[BFS] 게임 맵 최단거리 - Python

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

 

[문제 간단 요약]

1. (0, 0)에서 출발해 (n-1, m-1)까지 이동

2. maps[y][x] = 1은 이동 가능, 0은 벽

3. 최단 거리를 찾아야 하며, 이동은 상하좌우만 가능

4. 도달할 수 없다면 -1 반환

 

 

 

[문제 해결 방안]

1. 탐색 경로 중 가장 짧은 길이를 찾아야 한다는 문제 이므로, 최단거리 알고리즘(BFS) 사용

 

• 시작점 (0,0)부터 BFS로 인접 노드 탐색
• 벽이 아닌 (maps[y][x] == 1) 좌표만 다음 후보로 추가
• 방문했던 위치는 used[y][x]로 관리
• 목적지 (h-1, w-1)에 도달하면 이동 횟수 반환
• 도달 못할 경우 -1 반환

 

 

[문제 해결 코드 - python]

from collections import deque

def solution(maps):
    h = len(maps)
    w = len(maps[0])
    used = [[0]*w for _ in range(h)]
    q = deque()
    q.append((0, 0, 1))  # 시작 좌표와 거리
    used[0][0] = 1
    
    while q:
        y, x, cnt = q.popleft()
        if y == h - 1 and x == w - 1:
            return cnt
        for dy, dx in [[0,1], [0,-1], [1,0], [-1,0]]:
            ny, nx = y + dy, x + dx
            if 0 <= ny < h and 0 <= nx < w:
                if used[ny][nx] == 0 and maps[ny][nx] == 1:
                    used[ny][nx] = 1
                    q.append((ny, nx, cnt + 1))
    
    return -1

 

❓ DFS로는 해결 불가능?

=> 최단 거리 문제에서는 DFS가 부적합