[BOJ] #2178 미로 탐색 (BFS, Python)

0. 문제

2178번: 미로 탐색

 

1. BFS

이 문제를 BFS로 풀어야 하는 이유는 BFS는 시작 지점에서 가까운 노드부터 탐색하기 때문입니다. 이 문제는 (1, 1)에서 출발하여 (N, M)의 위치까지 이동할 때 지나야 하는 최소의 칸 수를 구해야 하므로 BFS 알고리즘으로 풀어야 적절합니다.

1. 우선, (0, 0)을 큐에 넣고 방문 처리합니다. (현재 queue: (0, 0))

2. 큐에서 (0, 0)을 빼고 (0, 0)에서 상하좌우로 움직일 수 있고 한번도 방문하지 않은 칸을 큐에 넣고 방문처리한 후, 그래프의 값을 (0, 0)의 값에 1을 더한 값을 넣어줍니다. (현재 queue: (1, 0), (0, 1))

3. 큐에서 (1, 0)을 빼내고 (1, 0)에서 상하좌우로 움직일 수 있는 칸 중에 방문하지 않은 (2, 0)과 (1, 1)을 큐에 넣고 방문처리합니다. 최단거리를 계속해서 업데이트(현재 칸에서 +1)해줍니다.  (현재 queue: (0, 1), (2, 0), (1, 1))

4. 큐에서 (0, 1)을 빼고 (0, 1)에서 상하좌우로 움직일 수 있는 칸인 (0, 0), (1, 1) 중에 방문하지 않은 칸이 없으므로 큐 삽입은 하지 않습니다.

5. 큐에 아무것도 없을 때까지 반복하여 탐색한 후, 마지막으로 최종 목적지 칸에 들어가 있는 값을 출력합니다.

 

2. 풀이 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 2178 미로탐색

from collections import deque

n, m = map(int, input().split())
graph = []
visited = [[False for _ in range(m)] for __ in range(n)]

for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 방향 정의(상 -> 하 -> 좌 -> 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 알고리즘
def bfs(graph, v, visited):
    queue = deque([v])
    visited[v[0]][v[1]] = True
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 공간을 벗어난 경우 무시
            if nx < 0 or ny < 0 or nx > n - 1 or ny > m - 1:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if visited[nx][ny] == False:
                visited[nx][ny] = True
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n - 1][m - 1]

print(bfs(graph, (0, 0), visited))