백준 2178번 미로 탐색 파이썬 BFS

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

2178번: 미로 탐색

 

 

내 답안

from collections import deque

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 nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
                
            # 0인 경우 무시
            if graph[nx][ny] == 0:
                continue
            
            # 1인 경우 카운트를 하나씩 해줌 (최단 거리 기록)
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n - 1][m - 1]  # n, m 최단거리 return
    
n, m = map(int, input().split())

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

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

print(bfs(0,0))

---

 

Review

 

이 문제는 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다.

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

따라서 (0,0) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다.

이해하기 위해 직접 문제의 예제를 손으로 그리며 생각을 하였다.

 

step 1 : 맨처음 1행1열부터 BFS 시작한다. ( queue = [ (0, 0) ] )

step1

 

step 2 : (0, 0) 에서 상 하 좌 우 탐색을 진행하며 새롭게 방문하면 자기 노드 번호 + 1 을 해준다.

            방문 처리를 한 노드는 연두색으로 칠해준다.       ( queue = [ (0, 0), (2, 0) ] )

step2

 

step 3 : step 2 와 같이 BFS 를 반복 해준다.  ( queue = [ (3, 0) ] )

 

step 4 : step 2 와 같이 BFS 를 반복 해준다.  ( queue = [ (3, 1) ] )

step 4

.

.

.

.

final step : 반복적으로 BFS 를 계속 수행하면 결과적으로 다음과 같이 최단 경로의 값들이 1씩 증가하는 형태로 변경된다.  ( queue = [ ] )

queue 가 비었으니 (n, m)의 최단경로 값을 반환해주고 함수는 종료 된다.

final step