2021.2.15 [백준] 미로 탐색

BFS 알고리즘

 

 

Q

 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

A

 

BFS를 이용하여 풀었다. 이코테 책에 있는 실전문제와 같아서 쉬웠다.

 

코드

 

from collections import deque

def bfs(x, y):

    queue = deque(()) #큐 구현을 위해 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 nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
                
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1

                queue.append([nx, ny])

 

    return graph[n - 1][m - 1]
    
n, m = map(int, input().split())
graph = [0] * n #m이 아니라 n인거 주의!!
for i in range(n):
    graph[i] = list(map(int, input()))

dx = [-1, 1, 0, 0] #상 하 좌 우 움직임 표현
dy = [0, 0, -1, 1] #상 하 좌 우 움직임 표현

print(bfs(0,0))