백준 2178 미로 탐색 (BFS, 최단 경로 탐색, 행렬그래프)

이번 문제는 BFS를 어떻게 최단경로로 활용할건지 이해해야한다. 처음에는 나도 BFS로 어떻게 최단경로를 구한다는 소리인지 알 수 없었다.

나도 완벽하게 이해하고 풀지 않았기 때문에 생각의 흐름을 나열해 볼까 한다.

우선 행렬그래프를 BFS의 트리 형태로 나열한다고 가정한다면 다음과 같은 그래프를 만들 수 있다. 그렇다면 우리는 (4,4)가 되기 위해서 7층까지 내려가야한다는 것을 단숨에 확인 가능하다.

그렇다면 BFS로 탐색을 하면서 언제가 몇층인지를 알아야한다. 따라서 층을 함께 표기해본다.

그러면 (1,1)이 1층인것을 알기 때문에 층에 큐에 넣은 인접 행렬에 대해서 2층이라는 것을 표기하여 큐에 삽입할 수 있다. 이러한 방식으로 (4,4)까지 진행하면 간단히 (4,4)가 7층에 있는 것을 알 수 있다.

 

탐색을 수행할 때 패딩을 넣어 탐색을 진행하면 더욱 쉽게 코딩할 수 있다.

또한 n,m이 언제 나오는지 if로 걸러주면 마지막에 원하는 층을 바로 출력가능하다.

 

이를 코드로 작성하면 아래와 같다.

from collections import deque
import time
n,m = map(int, input().split())
L = []
for i in range(n):
    tmp = [0] + list(map(int, list(input()))) + [0]
    L.append(tmp)
# 패딩 추가
L = [[0 for i in range(m+2)]] + L + [[0 for i in range(m+2)]]

BFS = deque([(1,1,1)])
out = []
num = 0
while BFS:
    t = BFS.popleft()
    if t not in out:
        out.append(t)
        i,j,z = t
        # 들렀기 때문에 제거
        L[i][j] = 0
        tmp = []
        # 동서남북 확인
        if L[i][j+1] == 1: #동
            tmp += [(i,j+1,z+1)]
        if L[i][j-1] == 1: #서
            tmp += [(i,j-1,z+1)]
        if L[i-1][j] == 1: #남
            tmp += [(i-1,j,z+1)]      
        if L[i+1][j] == 1: #북
            tmp += [(i+1,j,z+1)]
        tmp.sort()
        BFS += tmp
        if i == n and j == m:
            num = z
print(num)

결과적으로 BFS는 최단경로를 구할때 자주 사용된다는 것을 알 수 있었다.

 

이번에도 스터디 때문에 다시 풀어보았다. 코드도 줄었고 시간도 줄어서 기뻤다.

from collections import deque
n,m = map(int, input().split())
Map = []
for i in range(n):
    Map.append(list(map(int, input())))

def BFS():
    queue = deque([[0,0]])
    dx = [0,0,1,-1] # 동서남북
    dy = [1,-1,0,0]
    count = 0 
    while len(queue) != 0:
        count += 1
        for i in range(len(queue)):
            x,y = queue.popleft()
            if [x,y] == [n-1,m-1]:
                return count
            Map[x][y] = 0
            for _ in range(4):
                nx = x + dx[_]
                ny = y + dy[_]
                if nx<n and ny<m and 0<=nx and 0<=ny:
                    if (Map[nx][ny] == 1) and ([nx,ny] not in queue):
                        queue.append([nx,ny])
    return count
print(BFS())