[백준] 2178번 미로 탐색 BFS - 파이썬

 

 

문제

문제 설명

N×M 크기의 배열로 표현되는 미로가 있습니다.

예시:

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 '1'은 이동할 수 있는 칸을 나타내고, '0'은 이동할 수 없는 칸을 나타냅니다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하세요. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있습니다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함합니다.

입력

첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100)이 주어집니다. 다음 N개의 줄에는 M개의 정수로 미로가 주어집니다. 각각의 수들은 붙어서 입력으로 주어집니다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력합니다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어집니다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

힌트

주어진 예제에서 (1, 1)에서 (4, 6)까지의 최단 경로는 다음과 같습니다:

(1,1) → (2,1) → (3,1) → (4,1) → (4,2) → (4,3) → (3,3) → (2,3) → (1,3) → (1,4) → (1,5) → (2,5) → (3,5) → (4,5) → (4,6)

따라서, 지나야 하는 최소의 칸 수는 15칸입니다.

---

문제 풀이

BFS의 기본 코드에서 최단 경로 길이를 구하는 방법

N×M 크기의 배열로 표현되는 미로가기본 BFS 코드는 최단 경로의 존재 여부를 확인하는 데 중점을 둡니다. 하지만 이 문제에서는 최단 경로의 길이를 알아내는 것이 중요합니다. 기본 BFS 알고리즘을 약간 수정하여, 각 노드까지 도달하는 최단 거리를 기록함으로써 이를 해결할 수 있습니다. visited 배열에 각 위치까지의 이동 횟수를 저장하여, 탐색이 끝난 후 최종 목적지에 기록된 값을 반환함으로써 최단 경로의 길이를 구할 수 있습니다.

기본 BFS 코드

def bfs(start):
    queue.append(start)
    x, y = start[0], start[1]
    visited[y][x] = 1

    while queue:
        x, y = queue.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + i, y + j
            if 0 <= nx < M and 0 <= ny < N and map[ny][nx] != 0 and visited[ny][nx] == 0:
                queue.append((nx, ny))
                visited[ny][nx] = 1

문제의 정답 코드

def bfs(start):
    queue.append(start)
    x, y = start[0], start[1]
    visited[y][x] = 1

    while queue:
        x, y = queue.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + i, y + j
            if 0 <= nx < M and 0 <= ny < N and map[ny][nx] != 0 and visited[ny][nx] == 0:
                queue.append((nx, ny))
                visited[ny][nx] = visited[y][x] + 1
    return visited[N-1][M-1]

---

추가된 부분 및 설명

1. 최단 거리 계산을 위한 visited 배열의 변경
   • 기본 BFS: 방문 여부를 표시하기 위해 visited[ny][nx] = 1로 설정합니다.
   • 문제의 정답: 해당 노드까지의 최단 거리를 저장하기 위해 visited[ny][nx] = visited[y][x] + 1로 설정합니다.
   설명: 기본 BFS에서는 단순히 노드의 방문 여부만 체크합니다. 그러나 이 문제에서는 시작 지점부터 각 노드까지의 이동 횟수를 알아야 하므로, visited 배열에 이동 횟수를 누적하여 저장합니다. 이렇게 하면 BFS의 특성을 이용해 최단 경로의 거리를 계산할 수 있습니다.

---

결론

기본적인 BFS 알고리즘에 노드까지의 이동 횟수를 기록하는 로직을 추가하여, 시작점부터 목적지까지의 최단 거리를 계산할 수 있습니다. 이러한 변경을 통해 문제에서 요구하는 최소 칸 수를 정확히 구할 수 있습니다.