[Python]프로그래머스 - 게임 맵 최단거리

1. 문제정보

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

2. 풀이

전형적인 DFS/BFS 문제와 비슷하지만 목적지까지 도착하지 못하는 경우, 경로가 분리되는 경우 더 짧은 거리를 출력하는 것을 고려해야 하는 문제였다. 이미 방문한 노드(0 도아니고 1도 아닌)에 대해서 최단 거리를 갱신할 수 있는 경우에만 다음 노드를 추가하였다.

 

3. 소스코드

from collections import deque
def solution(maps):
    n, m = len(maps), len(maps[0])
    
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    
    q = deque()
    q.append([0, 0])
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            
            # 처음 방문한 노드, 이전 노드까지 이동한 거리 +1
            if maps[ny][nx] == 1:
                q.append([nx, ny])
                maps[ny][nx] = maps[y][x]+1
            # 이미 방문한 적이 있는 노드인 경우, 더 빠른 경로인 경우만 큐에 추가
            elif maps[ny][nx] != 0 and maps[ny][nx] != 1:
                if maps[y][x]+1 < maps[ny][nx]:
                    q.append([nx, ny])
                    maps[ny][nx] = min(maps[ny][nx], maps[y][x]+1)

    # 목적지까지 이동한 횟수
    answer = maps[n-1][m-1]

    # 목적지까지 이동 가능한 경우 이동횟수가 최소 2이상일 수 있음,
    if answer == 1:
        answer = -1
    return answer

 

 

4. 배운점

일반적인 경우와 달리 방문했던 노드를 재 방문하는 경우에 대해 생각해볼 수 있는 문제였다.