Lv2. 게임 맵 최단거리

코딩테스트 연습 > 게임 맵 최단거리

1. 풀이 설명

1. 전형적인 BFS문제다. 방향좌표 dx, dy 를 활용하여 map 을 최단거리로 이동해야 한다.

2. visited 리스트에는 현재 위치에 거리가 저장된다.
   visited[0][0] = 1 로, queue 에는 (0, 0) 을 넣어 초기화한다.

3. queue 의 아이템을 하나씩 빼면서 비지 않을 때 까지 돌고,
   queue 에서 빼낸 현재 위치에서 방향좌표에 따라 한 step 씩 움직이며
   visited와 queue 를 업데이트 한다.

4. visited 의 마지막 위치(visited[-1][-1])를 반환한다.

2. 나의 풀이

python

import collections

def solution(maps):
    return bfs(maps)

def bfs(maps):
    dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
    n, m = len(maps), len(maps[0])
    visited = [[-1] * m for _ in range(n)] 
    visited[0][0] = 1
    queue = collections.deque([(0, 0)])
    
    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if visited[ny][nx] == -1 and maps[ny][nx] == 1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append((ny, nx))
    
    return visited[-1][-1]    

3. 배운점

1. 행렬 map을 다룰 때 주의할 점
   n * m 행렬에서 행 == n == y 이다.
   위치를 표현할 때 (x, y) 라고 말하지만 실제 x 위치에는 행에 해당하는 y 를 놓고 문제를 풀어야 한다.

2. 아래 둘은 다르다.

visited = [[-1] * m] * n

visited = [[-1] * m for _ in range(n)]