문제 설명
각 값이 다음과 같은 의미를 가지는 2차원 행렬이 주어졌다고 가정해 봅시다.
- 0: 빈 칸(이동 가능)
- 1: 벽(지나갈 수 없음)
- 2: 사람
사람은 한 번의 시간 단위 동안 위, 아래, 왼쪽, 오른쪽 네 방향 중 하나로 이동하거나 제자리에 머무를 수 있습니다. 목표는 모든 사람이 만나는 데 걸리는 시간을 최소화하는 이동 가능한 칸을 찾아, 그 최소 시간을 반환하는 것입니다. 이때 여러 명이 같은 빈 칸을 동시에 지나갈 수 있으며, 임의의 두 사람 사이에는 항상 경로가 존재한다고 가정합니다.
예시
입력 행렬이 다음과 같다면:
| 2 | 0 | 1 | 0 |
| 1 | 0 | 0 | 2 |
| 2 | 0 | 2 | 0 |
출력은 2가 됩니다. 모든 사람이 matrix[1][1] 위치에 최대 2단계 만에 도착해 만날 수 있기 때문입니다.
풀이 접근법
이 문제는 각 사람의 위치에서 시작하는 BFS(너비 우선 탐색)를 활용해 해결할 수 있습니다.
bfs(r, c)함수를 정의합니다. 시작 좌표 (r, c)를 받아 해당 지점에서 각 칸까지의 거리를 계산합니다.- 큐(queue)를 생성하고 시작 좌표 (r, c)를 삽입합니다.
- 거리 맵
dist를{(r, c): 0}으로 초기화합니다. - 큐에서 좌표를 하나씩 꺼내며 다음을 반복합니다.
- 현재 거리가 15보다 크면 탐색을 중단합니다.
- 상하좌우 이웃 좌표 (nr, nc)를 확인하고, 아직 방문하지 않은 칸이라면 거리를 1 증가시켜 기록하고 큐에 추가합니다.
- 완성된 거리 맵
dist를 반환합니다.
메인 로직에서는 다음 과정을 수행합니다.
dist를 None으로 초기화합니다.- 행렬을 순회하며 값이 2(사람)인 칸마다 BFS를 실행합니다.
- 첫 번째 사람이라면 그 결과를
dist로 설정하고, 이후 사람부터는 모든 사람이 공통으로 도달 가능한 칸만 남기며, 각 칸의 거리는 사람별 거리의 최댓값으로 갱신합니다. 공통으로 도달할 수 없는 칸은 삭제합니다. - 마지막으로
dist에 남은 값들 중 최솟값을 반환합니다(모든 사람이 만나는 데 필요한 최소 시간).dist가 비어 있다면 0을 반환합니다.
예제 코드
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def get_neighbor(r, c):
for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
yield nr, nc
def bfs(r, c):
queue = [(r, c)]
dist = {(r, c): 0}
for r, c in queue:
if dist[r, c] > 15:
break
for nr, nc in get_neighbor(r, c):
if (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return dist
dist = None
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 2:
ndist = bfs(r, c)
if dist is None:
dist = ndist
else:
for key in list(dist.keys()):
if key in ndist:
dist[key] = max(dist[key], ndist[key])
else:
del dist[key]
return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
print(ob.solve(matrix))입력
[ [2, 0, 1, 0], [1, 0, 0, 2], [2, 0, 2, 0] ]
출력
2