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

# Baekjoon 2178번: 미로 탐색
import sys
from collections import deque 
input = sys.stdin.readline

N, K = map(int, input().split())
maze = [[] for _ in range(N)]
visited = [[] for _ in range(N+1)]

for i in range(N):
    for j in range(K):
        visited[i].append(0)
        
for i in range(N):
    maze_num = input()
    for j in maze_num:
        maze[i].append(j)

def BFS():
    visited[0][0] = 1
    queue = deque()
    queue.append((0, 0))
    
    while queue:
        y, x = queue.popleft()
        
        if (y, x) == (N-1, K-1):
            return visited[y][x]
        
        for (j, i) in ((y-1, x), (y+1, x), (y, x-1), (y, x+1)):

            if 0 <= j < N and 0 <= i < K and visited[j][i] == 0 and maze[j][i] == '1':
                visited[j][i] = visited[y][x] + 1
                queue.append((j, i))

ans = BFS()
print(ans)
            
            

이 문제는 BFS 알고리즘 문제이다. 먼저 2차원 배열인 maze와 visited을 만들고 문제에서 주어진 미로 내용은 maze에, 방문 여부를 알기 위한 visited는 원소 0으로 이루어지도록 했다.
BFS 구현은 while문에 들어가기전에 (0, 0)의 위치는 이미 방문했음을 알려주도록 1로 초기화하고, queue에 처음 위치 (0,0)을 tuple 형태로 삽입헀다.
while문 안에서는 먼저 queue의 원소들을 추출하여 y와 x좌표를 목적지인 (N-1, K-1)과 비교하도록 한다. 같지 않을 경우에는 y, x좌표의 상하좌우 값들을 각각 방문은 했는지, index는 초과하지 않는지, maze 배열에서 ‘1’의 값을 가지는지를 따진 뒤 모두 만족할 경우 queue에 현재 위치를 추가해주도록 했다.