백준 2178번 미로 탐색 _ BFS (python)

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

2178번: 미로 탐색

미로탐색  BFS

이번에 풀어볼 문제는 BFS(Breadth First Search) 너비우선탐색에 관한 심화 문제랍니다.
이전 2667번에서 DFS를 활용하여 문제를 풀었었던 것 처럼 1260번에서 기본적으로 구현했었던 DFS와 BFS의 구현을 활용하면 쉽게 풀 수 있는데요,
혹시 BFS의 구현이 기본적으로 어려우신 분들은 제 이전 1260번 풀이 포스팅을 참고해주세요 :)

2020/03/15 - [Programming/백준 문제풀이] - 백준 1260번 DFS와 BFS (python 구현)

백준 1260번 DFS와 BFS (python 구현)

 

사실 이번 문제 잘 보니 이전 2667번의 문제와 형식이 매우 유사한데요. 때문에 저는 2667번 문제 풀이의 코드를 많이 사용하였답니다.

이 문제는 너비우선탐색을 하면서 미로를 빠져 나갈 때 양쪽 출입구로부터의 최단 거리를 구하는 문제였는데요, 아마도 이 문제가 어려우셨던 분들은 대부분 어떻게 목표 도착위치까지 가느냐보다는 어떻게 최소 이동횟수를 카운트하느냐였을 겁니다.

저는 여기서 위상정렬의 개념을 약간 이용해줬어요.
예를 들어 A->B->C->D로 간다고 하면 A는 1차, B는 2차, C는 3차, D는 4차로 방문되겠죠?
이렇게 각 노드에서 몇번째 차수로 방문되었는지를 기록하는 배열을 하나 만들어주었답니다.
B에는 A의 차수 +1,  C에는 B의 차수 +1 형태로 더해주다보면 결국 저희는 최종적으로 목표 도착위치 노드의 차수가 최소 이동횟수가 되겠죠?

아마 이 부분 말고는 BFS의 구현 외에는 큰 어려움이 없으셨을거라 믿고 바로 풀이를 보여드릴게요!

[N, M] = list(map(int, input().split())) // N과 M입력
maze = [] // 미로 입력
visited = [[0 for _ in range(M)] for _ in range(N)] // 방문했는 지 확인
counter = [[0 for _ in range(M)] for _ in range(N)] // 차수 입력
Q = [] // 방문순서를 기록하는 큐

for i in range(N):
    maze.append(list(map(int, input()))) // 인풋받기

def BFS():
    while(len(Q)>0): //Q가 빌 때까지,
        [row, col] = Q.pop(0)

        if (row>0): // 4가지 방향 체크
            if (visited[row-1][col]==0 and maze[row-1][col] == 1): // 방문X, 미로 1
                Q.append([row-1,col]) // 방문순서에 추가한 후
                visited[row-1][col]=1 // 방문기록에 추가하고
                counter[row-1][col] += counter[row][col]+1 // 차수를 기록한다.

        if (col>0):
            if (visited[row][col-1]==0 and maze[row][col-1] == 1):
                Q.append([row,col-1])
                visited[row][col-1]=1
                counter[row][col-1] += counter[row][col]+1

        if (row<N-1):
            if (visited[row+1][col]==0 and maze[row+1][col] == 1):
                Q.append([row+1,col]) 
                visited[row+1][col]=1
                counter[row+1][col] += counter[row][col]+1

        if (col<M-1):
            if (visited[row][col+1]==0 and maze[row][col+1] == 1):
                Q.append([row,col+1])
                visited[row][col+1]=1
                counter[row][col+1] += counter[row][col]+1

        
Q.append([0,0]) // 시작노드 입력
visited[0][0] = 1
counter[0][0] = 1
BFS()
print(counter[N-1][M-1]) // 목표지점의 차수 출력

 

끝