#163 백준 파이썬 [2178] 미로 탐색 - BFS

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

 

#Solution

BFS, 그래프의 너비 우선 탐색 방법을 이용해 풀 수 있다. 큐를 이용하는 방법이다.

다음과 같은 알고리즘으로 푼다.

 

0) 방문한 노드를 담을 visited, 임시적으로 bfs를 돌릴 queue, 해당 노드까지의 거리를 담을 distance 리스트를 만들어준다.

1) maze의 0,0부터 시작해서 상하좌우의 길을 찾아준다.

 

-이하 반복

2) 현재 노드는 visited에 넣어준다.

3) 현재 노드의 상하좌우에 길이 있을 경우 queue에 넣어주고 해당 노드의 distance에 현재 노드+1을 넣어준다.

4) queue의 맨앞 노드를 pop하여 다음 노드로 사용한다.

 

5) 출구인 distance[N-1][M-1]의 값을 출력한다.

 

#BFS로 미로 탈출 알고리즘 정의
def bfs(maze, i, j, N, M):
    visited = [] #방문한 노드
    queue = [[i, j]] #BFS로 사용될 큐
    distance = [[0 for _ in range(M)] for _ in range(N)] #해당 지점까지의 거리를 담는 리스트
    distance[0][0] = 1 #첫 시작은 1
    
    while queue: 
        [i, j] = queue.pop(0) #BFS 큐에 넣어줌
        visited.append([i, j]) #방문 리스트에 쌓아줌
        
        #상하좌우 탐색
        if i < N-1 and maze[i+1][j] == 1 and [i+1, j] not in visited and [i+1, j] not in queue:
            queue.append([i+1, j])
            distance[i+1][j] = distance[i][j] + 1
        if j < M-1 and maze[i][j+1] == 1 and [i, j+1] not in visited and [i, j+1] not in queue:
            queue.append([i, j+1])
            distance[i][j+1] = distance[i][j] + 1
        if j > 0 and maze[i][j-1] == 1 and [i, j-1] not in visited and [i, j-1] not in queue:
            queue.append([i, j-1])
            distance[i][j-1] = distance[i][j] + 1
        if i > 0 and maze[i-1][j] == 1 and [i-1, j] not in visited and [i-1, j] not in queue:
            queue.append([i-1, j])
            distance[i-1][j] = distance[i][j] + 1
            
    return distance[N-1][M-1] #마지막 도착지의 거리를 반환


#Input담기
N, M = map(int, input().split())
maze = []
for _ in range(N): #미로를 2차원 배열로 받음
    maze.append(list(map(int, str(input()))))

#정답 출력
print(bfs(maze,0,0,N,M))