[백준] 2178번 미로 탐색 / 파이썬 python 너비 우선 탐색(bfs) 구현

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

 

백준 2178번 미로 탐색

 

간단한 너비 우선 탐색(bfs)으로 구현이 가능한 문제였다.

 

너비 우선 탐색(breadth-first search) 알고리즘 특징은 그래프의 완전 탐색 방법 중 하나로,

가까운 노드를 먼저 방문한다.

 

스택, 재귀를 사용하는 깊이 우선 탐색(depth-first search)과 다르게 너비 우선 탐색은

선입선출(First In First Out) 방식이므로 큐를 사용해서 구현한다.

 

 

문제

 

 

 

 

설명

 

출발점 (0, 0)에서 상,하,좌,우를 봤을 때, 1이 있으면 현재 내가 있는 값 + 1 을 해준다.

 

 

도착점 (N-1, M-1)에 도달했을 때 그 값을 출력해 주면 끝.

 

코드가 짧고 어렵지 않으므로 바로 소스를 보며 이해하겠다.

 

 

코드

 

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, ' '.join(input().split()))) for _ in range(n)]

# 상하좌우 탐색용
dx = [0,1,0,-1]
dy = [-1,0,1,0]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:		# 좌표 유효성 검사
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0,0))