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

🗂️ 문제

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

프로그래머스

 

💡 접근법

최단거리를 구하기 위해 BFS를 사용한다.

이때 상하좌우로 이동하면서 맵을 탐색해야 한다. 따라서 변화량을 나타내는 dx와 dy 리스트를 생성한다.

 

초기 시작 위치를 (0, 0)으로 지정하고, 시작 위치에서부터 상하좌우로 탐색한다. 탐색하면서 조건문을 통해 맵을 벗어나지 않는지, 벽이 아닌지, 방문한 적이 없는지 확인한다.

위 조건을 모두 만족할 경우 방문 처리를 수행하고, 맵의 현재 위치에 거리를 업데이트한다.

 

모든 탐색을 마친 후 최종 도착지까지의 거리가 1이면 상대팀 진영에 도착하지 못한 경우이므로 -1을 리턴하고, 거리가 1이 아닐 경우 도착지까지의 최단 거리를 리턴한다.

 

😎 내 코드

from collections import deque

def solution(maps):
    N = len(maps)
    M = len(maps[0])

    visited = [[False] * (M) for _ in range(N)]
    
    dx = [1, -1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    
    def BFS():
        queue = deque()
        queue.append((0, 0))
        visited[0][0] = True
        
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M:  # 맵을 벗어나지 않는지 확인
                    if maps[nx][ny] and not visited[nx][ny]:  # 맵이 벽이 아니면서 방문한 적 없는지 확인
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                        maps[nx][ny] = maps[x][y] + 1  # 거리 업데이트
            
    BFS()
    
    if maps[N-1][M-1] == 1:
        return -1
    else:
        return maps[N-1][M-1]

 

🧐 배운 점

1. 맵의 크기만큼 방문 배열(visited)를 미리 False로 선언해두고 방문 처리하는게 방문 배열에 맵의 좌표를 넣는 것보다 더 효율적이다.
   • 맵의 크기만큼 방문 배열(visited)를 미리 False로 선언해두고 방문 처리하는 방식
     • if not visited[nx][ny]
     • visited = [[False] * M for _ in range(N)]
   • 방문 배열에 맵의 좌표를 넣는 방식
     • if (x,y) not in visited
     • visited.append((x, y))
2. 최단 거리를 구하기 위해서는 새로운 좌표에 방문할 때마다 거리를 업데이트해야 한다.

 

💡 ETC

최단 거리를 구하는 문제이므로 BFS로 구현하면 바로 풀 수 있다.

하지만 이때 DFS로도 풀 수 있지 않을까 생각했다. 따라서 DFS 기반 구현을 시도했지만, 테스트 도중 몇 개의 경우에 대해서는 오답 처리가 되었다. 구현 코드와 그 이유는 다음과 같다.

 

DFS 기반 구현 코드

def solution(maps):
    N = len(maps)
    M = len(maps[0])
    
    visited = [[False] * M for _ in range(N)]
    xlist = [0, 0, -1, 1]  # 상하좌우
    ylist = [1, -1, 0, 0]
    
    def DFS(x, y):
        if (x, y) not in visited:
            visited[x][y] = True
            
            for ax, ay in zip(xlist, ylist):
                nx = x + ax
                ny = y + ay
                if N > nx >= 0 and M > ny >= 0:
                    if maps[nx][ny] == 1 and not visited[nx][ny]:
                        maps[nx][ny] = maps[x][y] + 1
                        DFS(nx, ny)
    
    DFS(0, 0)
    
    if maps[N-1][M-1] == 1:
        return -1
    else:
        return maps[N-1][M-1]

 

그 이유

“최단 거리를 탐색하지 못함”

• DFS는 깊이 우선으로 탐색하므로, 한 경로를 끝까지 쭉 따라가다가 막히면 다시 돌아오고 다른 경로를 살피게 된다. 즉, “먼 경로”부터 거리값이 갱신될 수 있다.
• 따라서 먼저 찾은 경로가 최단 경로가 아닐 수도 있고, 이미 큰 거리로 갱신된 뒤에 더 짧은 경로를 찾을 가능성도 있지만, 그때는 이미 (x, y) 값이 더 큰 값으로 덮여서 원하는 결과를 업데이트하지 못하게 될 수 있다.
  • (nx, ny)에 큰 거리값(예: 7)을 기록해 두었을 때, “짧은 경로”를 통해 (nx, ny)에 다시 도달한다고 해도 이미 방문 처리(또는 거리값 기록)가 되어 있어서 새로운(더 작은) 거리로 갱신되지 않거나, 혹은 코드 로직상 이미 방문한 노드를 다시 방문하거나 다시 거리 갱신하지 않도록 되어 있으면 더 짧은 거리로 덮어쓸 수 없음.
• 반면, BFS는 너비 우선으로, 시작점에서 가까운 노드(거리 1) → 그 다음 거리 2 → 거리 3 순으로 단계적으로 진행하기 때문에 먼저 방문하는 노드의 거리는 무조건 가장 짧은 거리가 되고, 한 번 거리값을 기록한 뒤에는 그보다 긴 거리로는 다시 갱신될 일이 없다.

⇒ 결과적으로, DFS는 무조건 최단 거리를 찾는다는 보장이 없다. 
(물론 몇 가지 조건을 추가하면 구현은 가능하겠다만… 굳이? 싶다.)

 

🔗 참고 레퍼런스

• [Programmers / Java] 게임 맵 최단거리 (DFS/BFS)