(Python) 백준 2178번 : 미로 탐색

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

2178번: 미로 탐색

---

 

(Python) 백준 2178번 : 미로탐색¶

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

※ 알고리즘 분류

• BFS

---

In [1]:

from collections import deque

# 입력값 받기
N,M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]

4 6
101111
101010
101011
111011

In [2]:

print("N={}, M={}".format(N,M))
maze

N=4, M=6

Out[2]:

[[1, 0, 1, 1, 1, 1],
 [1, 0, 1, 0, 1, 0],
 [1, 0, 1, 0, 1, 1],
 [1, 1, 1, 0, 1, 1]]

In [3]:

def bfs(N, M, graph):
    visited = [] # 방문 기록
    q = deque() 
    q.appendleft([[0,0],1]) # [[x,y좌표], cnt(이동횟수)]
    
    dx = (-1,0,1,0)
    dy = (0,1,0,-1)
    while(q):
        node = q.pop() # 현재 방문하고 있는 node
        # 방문한 기록이 있는지 확인
        if node[0] not in visited:
            visited.append(node[0]) # 방문 기록
            for i in range(4): # 현재 노드 기준으로 동서남북 네 방향에 대해 bfs
                new_x = node[0][0] + dx[i]
                new_y = node[0][1] + dy[i]
                # 조건충족시 이동 가능하다.
                if 0<=new_x<N and 0<=new_y<M and graph[new_x][new_y]==1:
                    # 출구에 도착했는가?
                    if new_x==N-1 and new_y==M-1:
                        return node[1] + 1
                    # 출구에 도착한 것이 아니라면 queue에 추가한다.
                    else:
                        q.appendleft([[new_x, new_y], node[1]+1])

In [4]:

bfs(N,M,maze)

Out[4]:

15