0은 물(water), 1은 땅(land)을 나타내는 이진 행렬(binary matrix)이 주어졌다고 가정해 보겠습니다. 이때 물로부터 맨해튼 거리(Manhattan distance)가 가장 먼 땅을 찾고, 그 거리 값을 반환하는 것이 이 문제의 목표입니다.
문제 예시
예를 들어 다음과 같은 행렬이 입력으로 주어진 경우를 살펴보겠습니다.
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
이 경우 출력 결과는 3입니다. [0, 0] 위치의 셀이 물로부터 맨해튼 거리 3만큼 떨어져 있기 때문입니다.
해결 접근 방법
이 문제는 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 모든 물 셀을 시작점으로 삼아 동시에 탐색을 확장해 나가면서, 각 땅 셀까지의 거리를 기록하는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- 행렬 A가 비어 있다면 0을 반환합니다.
- R := 행렬의 행 개수, C := 열 개수로 설정합니다.
- distance := R × C 크기의 행렬을 만들고 0으로 초기화합니다.
- q := 값이 0(물)인 모든 좌표 쌍 (r, c)을 담은 양방향 큐(deque)를 생성합니다.
- q의 크기가 0이거나 R × C와 같다면(모두 물이거나 모두 땅인 경우) -1을 반환합니다.
- q가 빌 때까지 다음을 반복합니다.
- (r, c) := q의 왼쪽 요소를 꺼내고 제거합니다.
- 상하좌우 인접 좌표 [(r-1, c), (r+1, c), (r, c+1), (r, c-1)]의 각 쌍 (x, y)에 대해 다음을 수행합니다.
- x와 y가 행렬 범위 내에 있고 A[x][y]가 1(땅)이라면:
- A[x][y] := 0으로 변경(방문 처리)
- distance[x][y] := distance[r][c] + 1 (거리 갱신)
- q의 끝에 (x, y)를 삽입합니다.
- x와 y가 행렬 범위 내에 있고 A[x][y]가 1(땅)이라면:
- res := 각 행의 최댓값들을 담은 리스트를 만듭니다.
- res 중 최댓값을 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
from collections import deque class Solution: def solve(self, A): if not A: return 0 R, C = len(A), len(A[0]) distance = [[0] * C for _ in range(R)] q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c]) if len(q) in (0, R * C): return -1 while q: r, c = q.popleft() for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]: if 0 <= x < R and 0 <= y < C and A[x][y]: A[x][y] = 0 distance[x][y] = distance[r][c] + 1 q.append((x, y)) return max(max(row) for row in distance) ob = Solution() matrix = [ [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 1] ] print(ob.solve(matrix))
입력
[ [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 1] ]
출력
3
알고리즘 동작 원리 정리
이 풀이의 시간 복잡도는 O(R × C)로, 행렬의 모든 셀을 한 번씩만 방문하기 때문에 매우 효율적입니다. 멀티 소스 BFS(Multi-source BFS) 방식을 사용하므로, 각 땅 셀에서 가장 가까운 물 셀까지의 거리가 자연스럽게 계산됩니다. 마지막으로 distance 행렬에서 최댓값을 찾으면 그것이 바로 '물에서 가장 먼 땅'의 맨해튼 거리가 됩니다. 참고로 행렬에 물이 전혀 없거나 땅이 전혀 없는 극단적인 경우에는 유효한 답이 존재하지 않으므로 -1을 반환하도록 처리했습니다.