문제 개요
2차원 행렬(matrix)에 다음과 같은 값들이 있다고 가정해 보겠습니다.
0 : 빈 칸을 나타냅니다.
1 : 벽을 나타냅니다.
2 : 사람을 나타냅니다.
사람은 상하좌우 네 방향(위, 아래, 왼쪽, 오른쪽)으로 자유롭게 이동할 수 있습니다. 우리가 구해야 할 것은 벽이 아닌 칸 중에서 모든 사람이 그 칸까지 걸어가는 총 이동 거리의 합을 최소화하는 위치이며, 마지막으로 그 최소 거리 값을 반환하는 것입니다.
예를 들어 입력이 다음과 같다면,
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
출력은 7이 됩니다. 최적의 만남 지점은 행렬의 오른쪽 아래 모서리이기 때문입니다.
해결 알고리즘
이 문제는 각 사람의 위치에서 시작하는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
사람의 위치를 저장할 맵
twos와, 사람별 거리 비용을 저장할 맵costs를 생성합니다.행렬의 각 행
r과 인덱스i, 그리고 각 값v와 인덱스j를 순회하며, 값이 2인 경우 다음을 수행합니다.twos[(i, j)]에 시작점[i, j, 0]을 담은 큐를 저장합니다.costs[(i, j)]에는 행렬과 같은 크기의 무한대(∞)로 채워진 2차원 거리 행렬을 생성합니다.
twos의 각 키-값 쌍(k, q)에 대해 다음을 반복합니다.방문 여부를 추적하기 위한 집합
seen을 생성합니다.큐
q가 빌 때까지 다음을 반복합니다.큐의 첫 번째 원소
(i, j, cost)를 꺼냅니다.(i, j)가 이미seen에 있다면 다음 반복으로 넘어갑니다.(i, j)를seen에 추가하고,costs[k][i][j]에 현재 비용을 기록합니다.네 방향
((1, 0), (-1, 0), (0, 1), (0, -1))에 대해 인접 좌표(ni, nj)를 계산하고, 좌표가 행렬 범위 내에 있으며 벽(1)이 아니라면(ni, nj, cost + 1)을 큐 뒤에 삽입합니다.
정답 변수
ans를 무한대로 초기화한 뒤, 행렬의 모든 칸(i, j)에 대해 각 사람의 거리 비용 합cur_cost를 계산하고,ans와 비교하여 더 작은 값을 저장합니다.최종적으로
ans를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, matrix):
twos = {}
costs = {}
for i, r in enumerate(matrix):
for j, v in enumerate(r):
if v == 2:
twos[(i, j)] = [(i, j, 0)]
costs[(i, j)] = [[1e9 for _ in matrix[0]] for _ in matrix]
for k, q in twos.items():
seen = set()
while q:
i, j, cost = q.pop(0)
if (i, j) in seen:
continue
seen.add((i, j))
costs[k][i][j] = cost
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if (ni >= 0 and nj >= 0 and ni < len(matrix) and nj < len(matrix[0]) and matrix[ni][nj] != 1):
q.append((ni, nj, cost + 1))
ans = 1e9
for i in range(len(matrix)):
for j in range(len(matrix[0])):
cur_cost = 0
for arr in costs.values():
cur_cost += arr[i][j]
ans = min(ans, cur_cost)
return ans
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 1, 2],
[0, 0, 2, 2]
]
print(ob.solve(matrix))
입력
matrix = [
[2, 0, 1, 0],
[1, 0, 1, 2],
[0, 0, 2, 2]]
출력
7
정리
이 알고리즘은 각 사람의 위치에서 BFS를 한 번씩 수행하므로, 시간 복잡도는 사람의 수를 P, 격자의 크기를 N×M이라 할 때 O(P × N × M)입니다. 각 칸까지의 최단 거리를 미리 계산해 두고 마지막에 합산만 하기 때문에, 벽으로 막힌 지형에서도 모든 사람의 총 이동 거리를 최소화하는 최적의 만남 지점을 정확하게 찾아낼 수 있습니다.