원제: Minimum XOR Path in a Grid
| 플랫폼 | 문제 번호 | 난이도 | 언어 |
|---|---|---|---|
| 리트코드 | 3882 | 보통 (Medium) | Python 3 |
왼쪽 위 (0, 0)에서 시작해 오른쪽 또는 아래쪽으로만 이동하여 오른쪽 아래 (m - 1, n - 1)에 도달하는 경로 중, 경로에 포함된 모든 칸의 값의 비트 XOR가 가장 작은 값을 구합니다. 시작 칸과 도착 칸도 XOR에 포함하며, 반환값은 가능한 경로 비용의 최솟값입니다.
grid의 크기는 m * n이고 1 <= m == grid.length <= 1000, 1 <= n == grid[i].length <= 1000, m * n <= 1000입니다. 각 값은 0 <= grid[i][j] <= 1023입니다. 이동은 오른쪽 또는 아래쪽뿐입니다.
예제 1: grid = [[1,2],[3,4]]이면 두 경로의 XOR는 각각 1 XOR 2 XOR 4 = 7, 1 XOR 3 XOR 4 = 6이므로 출력은 6입니다. 예제 3: grid = [[2,7,5]]는 경로가 하나이고 2 XOR 7 XOR 5 = 0이므로 출력은 0입니다.
dp[i][j]를 (i, j)에 도달하는 모든 경로의 XOR 값을 모은 집합으로 둡니다. 같은 칸까지의 경로라도 XOR 값이 다르면 이후 칸에서 다른 결과를 만들 수 있으므로, 칸마다 하나의 최솟값만 저장하지 않고 집합 전체를 유지합니다. 각 경로는 바로 위나 왼쪽 칸 중 하나에서만 올 수 있으므로, 두 선행 칸의 XOR 값 각각에 현재 칸 값을 XOR한 결과가 현재 집합에 들어갑니다. 이렇게 모든 경로의 XOR를 빠짐없이 모은 뒤 도착 칸 집합의 최솟값을 반환합니다.
n = len(grid), m = len(grid[0])로 행과 열의 수를 구하고, dp는 각 칸에 대응하는 집합으로 만듭니다. dp[0][0].add(grid[0][0])은 시작 칸도 경로 비용에 포함한다는 점을 반영합니다.
행 i, 열 j 순서로 방문하며 시작 칸은 건너뜁니다. i > 0이면 dp[i-1][j]의 각 값 x에 대해 x ^ grid[i][j]를 추가하고, j > 0이면 dp[i][j-1]에도 같은 처리를 합니다. 두 조건은 격자 밖의 선행 칸을 참조하지 않게 하며, 가능한 이동이 아래와 오른쪽뿐이라는 조건을 그대로 반영합니다. set은 서로 다른 경로에서 같은 XOR 값이 나온 경우 중복 저장하지 않습니다. 마지막에 min(dp[n-1][m-1])을 반환합니다.
class Solution:
def minCost(self, grid: list[list[int]]) -> int:
n = len(grid)
m = len(grid[0])
dp = [[set() for i in range(m)] for i in range(n)]
dp[0][0].add(grid[0][0])
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
continue
if i > 0:
for x in dp[i-1][j]:
dp[i][j].add(x ^ grid[i][j])
if j > 0:
for x in dp[i][j-1]:
dp[i][j].add(x ^ grid[i][j])
return min(dp[n-1][m-1])
S를 전체 칸에서 각 dp[i][j]에 저장되는 서로 다른 XOR 값 수의 합, K를 한 칸에 저장될 수 있는 XOR 값의 최댓값이라고 두면, 시간은 각 선행 칸의 집합을 순회하므로 O(S)입니다. 값의 범위가 0부터 1023까지이므로 K <= 1024이고, 보조 공간은 집합에 저장하는 값 기준 O(mnK) 이하입니다. 격자 크기와 집합 객체의 공간을 포함하면 O(mn + S)입니다. 반환값 하나만 추가로 필요합니다.
행 인덱스가 n, 열 인덱스가 m으로 코드에서 정해져 있으므로 dp와 반복문의 순서가 이에 맞춰져 있습니다. m * n <= 1000 조건에서도 모든 경로를 개별 열거하지 않고, 각 칸에서 같은 XOR 결과를 집합으로 합칩니다. 도착점 집합에는 최소한 하나의 경로 값이 들어 있으므로 min을 계산할 수 있습니다.