[Python] 2178번 : 미로 탐색

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

2178번: 미로 탐색

 

문제 3줄 요약

 

1. 1은 길, 0은 벽

2. 좌측 상단에서 시작해서 우측 하단으로 이동한다.

3. 미로를 탈출하는 최소의 이동 칸 수를 구해라

 

---

문제가 매우 익숙하다!

 

전에 풀었던 델타 탐색을 사용하면 될 것 같은데,

델타 탐색이 뭔지 궁금하다면?

 

https://59travel.tistory.com/77

[Python] 2667번 : 단지번호붙이기

 

위 포스팅 글을 읽으면 도움이 될 것이다!

 

---

오늘은 단지번호붙이기 문제와 매우 유사한 문제이기 때문에

설명은 생략하고 바로 코드를 보도록 하자!

 

from sys import stdin
from collections import deque

# bfs + 델타 탐색
def bfs(x,y):
    bfs_deque, cnt = deque([(x,y,0)]), 0
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]

    while(len(bfs_deque) > 0):
        x, y, cnt = bfs_deque.popleft()

		# 미로 도착
        if (x == (N-1)) and (y == (M-1)):
            return cnt+1

        if visited[x][y]:
            visited[x][y] = 0
            
            for move in range(4):
                next_x = x+dx[move]
                next_y = y+dy[move]

                if (next_x>=0) and (next_x<N) and (next_y>=0) and (next_y<M):
                    if miro[next_x][next_y] and visited[next_x][next_y]:
                        bfs_deque.append((next_x,next_y, cnt+1))


N, M = map(int,stdin.readline().split())
miro, visited = [],[]

for _ in range(N):
    miro.append(list(map(int, stdin.readline().rstrip())))
    visited.append([1]*M)
print(bfs(0,0))

 

기존의 BFS 구조에 델타 탐색을 이용한

상하좌우에 길이 있다면, 탐색 경우의 수에 넣도록 작성하였다.

 

물론 visited로 방문 검사를 했을 때,

방문한 좌표라면 pass

 

바로 어제 올린 숨바꼭질 문제와 동일하게

큐에 값을 넣을 때, 튜플 형태로 좌표와 카운트 값을 넣어줘

Depth를 통한 이동 횟수를 계산한다.

 

좌표에 도착하면,

cnt 값을 반환해주며 마무리

 

끝!