[Python]Baekjoon 2178번: 미로 탐색(BFS)

1. 문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

2. 풀이

BFS 알고리즘을 활용하여 풀이할 것이다.

BFS 하면 queue바로 떠올려야 하고 queue하면 deque가 바로 떠올라야 한다.

행렬 역시 그래프로 생각할 수 있으므로 주어진 행렬을 그래프에 저장한다.

그래프에서 (N, M)까지 가는 길은 연결되어 있으므로 BFS 함수는 한번만 호출해주면 된다.

BFS 함수에서 우선 queue를 선언해주고 전달받은 좌표를 큐에 넣어준다.

큐를 순회하면서 좌표의 상하좌우가 조건에 맞다면 다음 좌표를 큐에 넣어주고

다음 칸으로 이동 했다는 의미로 +1을 해준다.

3. 코드

from collections import deque

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

graph = []

for _ in range (N):

graph.append(list(map(int, input().rstrip())))

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

def bfs(x, y):

queue = deque()

queue.append((x,y))

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 and graph[nx][ny] == 1:

queue.append((nx,ny))

graph[nx][ny] = graph[x][y] + 1

return graph[N-1][M-1]

print(bfs(0,0))

4. 느낀점

작년 2학기에 이러한 유형이 과제로 나왔었는데 해결하지 못했던 기억이 있다.

탐색하는 과정을 설계한다는 게 언제 봐도 쉽지 않은 일인 것 같다.

BFS 알고리즘의 형태에 조금 익숙해질 수 있었고, 익숙해질 때까지 비슷한 유형의 문제를 계속 풀어봐야 할 것 같다..

오늘 하루도 쌓였다.