이번 문제에서는 각 칸이 고유한 문자열로 이루어진 행렬(도시 블록 지도)과, 방문해야 할 블록 이름이 담긴 리스트가 주어집니다. 현재 위치가 matrix[0][0]일 때, 주어진 순서대로 모든 블록을 방문하기 위해 이동해야 하는 맨해튼 거리(Manhattan Distance)의 총합을 구하는 것이 목표입니다.
문제 예시
예를 들어 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
| q | b | c |
| d | e | z |
| g | h | i |
방문해야 할 블록 리스트는 다음과 같습니다.
blocks = ["h", "b", "c"]
이 경우 출력값은 6입니다. 그 이유는 다음과 같습니다.
- 시작 위치
matrix[0][0]에서 "h"까지: 아래쪽(남쪽)으로 2칸, 오른쪽(동쪽)으로 1칸 → 거리 3 - "h"에서 "b"까지: 위쪽(북쪽)으로 2칸 → 거리 2
- "b"에서 "c"까지: 오른쪽(동쪽)으로 1칸 → 거리 1
따라서 총 이동 거리는 3 + 2 + 1 = 6이 됩니다.
풀이 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 각 블록의 좌표를 저장할 맵(coords)을 만들고, 시작점 'start'의 값을 (0, 0)으로 초기화합니다.
- 행렬의 모든 칸을 순회하면서 각 문자열(블록 이름)에 해당하는 좌표 (row, col)를 coords에 저장합니다.
- 누적 거리를 저장할 변수 dist를 0으로 초기화합니다.
- 방문 블록 리스트 앞에 'start'를 추가하여 출발점부터 계산할 수 있도록 합니다.
- 인접한 두 블록 사이의 맨해튼 거리 |x1 - x2| + |y1 - y2|를 계산하여 dist에 더합니다.
- 모든 구간의 거리를 더한 최종 dist를 반환합니다.
구현 예제 코드
위 알고리즘을 Python으로 구현하면 다음과 같습니다.
class Solution:
def solve(self, mat, blocks):
coords = {'start': (0,0)}
for row in range(len(mat)):
for col in range(len(mat[row])):
coords[mat[row][col]] = (row,col)
dist = 0
blocks = ['start'] + blocks
for i in range(len(blocks)-1):
c1 = coords[blocks[i]]
c2 = coords[blocks[i+1]]
d = abs(c1[0]-c2[0]) + abs(c1[1]-c2[1])
dist += d
return dist
ob = Solution()
inp = [["q", "b", "c"],
["d", "e", "z"],
["g", "h", "i"]]
blk = ["h", "b", "c"]
print(ob.solve(inp, blk))입력
[["q", "b", "c"],["d", "e", "z"],["g", "h", "i"]]
출력
6
정리
이 풀이의 핵심은 두 가지입니다. 첫째, 딕셔너리를 활용해 각 블록의 좌표를 O(1) 시간에 조회할 수 있도록 한 점, 둘째, 맨해튼 거리 공식을 이용해 인접 블록 간 이동 거리를 단순히 누적했다는 점입니다. 전체 시간 복잡도는 좌표 매핑에 O(N×M), 거리 계산에 O(K)(K는 방문 블록 수)이므로 매우 효율적입니다.