[DFS & BFS] 게임 맵 최단거리

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

프로그래머스

 

보통 DFS는 완전 탐색에 사용되고, BFS는 최단 거리 계산에 사용되기 때문에 "게임 맵 최단거리" 문제는 BFS로 해결할 수 있습니다.

 

이 문제는 미로 탈출문제 유형입니다. 각 포인트마다 최단거리를 모두 구하고 마지막 graph[n - 1][m - 1]의 값을 반환하면 됩니다.

이동은 dx, dy 리스트에 상하좌우 이동 관련 좌표 변경 값을 넣어줍니다. 그리고 이 네 가지 방향으로 이동한 후 이동할 수 있는 포인트면 +1을 통해 거리를 기록합니다.

이 과정을 반복하면 시작점부터 각 포인트의 최단 거리를 계산할 수 있습니다.

이동시에는 공간을 벗어나지 않도록 좌표를 확인하는 조건문을 추가합니다.

(if nx < 0 or nx >= n or ny < 0 or ny >= m:)

 

추가로, 이 문제는 마지막까지 이동하기전에 블럭이 있다면 -1을 반환하라는 조건이 있습니다.

그래서 graph[n - 1][m - 1] 탐색 유무를 is_block 함수에 저장하면 해결할 수 있습니다.

 

from collections import deque


def bfs(graph, x, y, n, m):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    dq = deque()
    dq.append((x, y))
    
    is_block = False
    
    while dq:
        x, y = dq.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                # print(nx, ny, graph[nx][ny], graph[x][y] + 1)
                graph[nx][ny] = graph[x][y] + 1
                dq.append((nx, ny))
                
                if nx == n - 1 and ny == m - 1:
                    is_block = True
    
    return graph[n - 1][m - 1], is_block

def solution(maps):
    answer = 0
    
    dst, is_block = bfs(maps, 0, 0, len(maps), len(maps[0]))
    if is_block:
        answer = dst
    else:
        answer = -1
    
    return answer