0과 1로 이루어진 이진 행렬이 주어졌을 때, 각 셀의 값을 가장 가까운 0까지의 맨해튼 거리(Manhattan Distance)로 바꾼 행렬을 구하는 문제를 생각해 봅시다. 이때 행렬에는 최소한 하나 이상의 0이 존재한다고 가정합니다.
문제 예시
입력 행렬이 다음과 같다고 가정해 보겠습니다.
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
그렇다면 출력 결과는 다음과 같습니다.
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
왼쪽 아래 셀(값 1)은 가장 가까운 0까지의 거리가 2이므로 값이 2로 변경됩니다. 나머지 셀들은 인접한 0과의 거리가 그대로 유지됩니다.
해결 접근 방법: 두 번의 스캔으로 거리 갱신하기
이 문제는 동적 프로그래밍(DP) 기반의 두 패스(two-pass) 방식으로 효율적으로 해결할 수 있습니다. 알고리즘 단계는 다음과 같습니다.
- m := 행렬의 행 개수, n := 행렬의 열 개수로 설정합니다.
- 1단계 — 초기화: 모든 셀을 순회하면서 값이 0이 아닌 셀은 무한대(infinity)로 설정합니다. 이는 해당 셀이 아직 최단 거리를 알 수 없음을 의미합니다.
- 2단계 — 왼쪽 위 → 오른쪽 아래 순방향 스캔: 각 셀에 대해 위쪽 셀(y-1)과 왼쪽 셀(x-1)의 값에 1을 더한 것 중 최솟값으로 현재 셀을 갱신합니다.
- 3단계 — 오른쪽 아래 → 왼쪽 위 역방향 스캔: 반대 방향으로 순회하면서 아래쪽 셀(y+1)과 오른쪽 셀(x+1)의 값에 1을 더한 것 중 최솟값으로 현재 셀을 갱신합니다.
- 갱신이 완료된 행렬을 반환합니다.
순방향 스캔은 위쪽·왼쪽 방향에서 온 거리 정보를, 역방향 스캔은 아래쪽·오른쪽 방향에서 온 거리 정보를 반영합니다. 이 두 번의 스캔만으로 모든 방향의 최단 맨해튼 거리가 계산되며, 시간 복잡도는 O(m×n)입니다.
Python 구현 예제
import math class Solution: def solve(self, matrix): m, n = len(matrix), len(matrix[0]) # 0이 아닌 셀을 무한대로 초기화 for y in range(m): for x in range(n): if matrix[y][x]: matrix[y][x] = math.inf # 순방향 스캔: 위쪽, 왼쪽 방향 고려 for y in range(m): for x in range(n): if y: matrix[y][x] = min(matrix[y][x], matrix[y - 1][x] + 1) if x: matrix[y][x] = min(matrix[y][x], matrix[y][x - 1] + 1) # 역방향 스캔: 아래쪽, 오른쪽 방향 고려 for y in range(m - 1, -1, -1): for x in range(n - 1, -1, -1): if y + 1 < m: matrix[y][x] = min(matrix[y][x], matrix[y + 1][x] + 1) if x + 1 < n: matrix[y][x] = min(matrix[y][x], matrix[y][x + 1] + 1) return matrix ob = Solution() matrix = [ [1, 0, 1], [1, 0, 1], [1, 1, 0] ] print(ob.solve(matrix))
입력
[[1, 0, 1], [1, 0, 1], [1, 1, 0] ]
출력
[[1, 0, 1], [1, 0, 1], [2, 1, 0]]
정리
이 알고리즘은 BFS(너비 우선 탐색) 없이도 두 번의 선형 스캔만으로 각 셀의 최단 맨해튼 거리를 정확히 계산할 수 있습니다. 행렬 전체를 두 번만 순회하므로 시간 복잡도는 O(m×n), 공간 복잡도는 추가 배열 없이 원본 행렬을 재활용하므로 O(1)(입력 제외)입니다. 대규모 격자 데이터에서도 효율적으로 동작하는 실용적인 해법입니다.