61. Python 백준 2178 번 미로 탐색

안녕하세요 코딩하는 덕구입니다.

Python 백준 2178 번 미로 탐색 입니다.

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

2178번: 미로 탐색

 

DFS, BFS 아무거나 사용하면 되는거 아니냐고 하실 수 있는데

DFS를 마구잡이로 사용하시면 안됩니다.

마구잡이로 사용하면 최단거리가 아닌 첫 번째로 해결하는 값이 출력되기 때문이죠

 

최단거리 문제는 BFS 로 푸시면 됩니다.

입구 부분에서 출구 부분에 가까워지면서 최단거리를 구할 수 있기 때문이죠.

 

BFS는 Queue로 구현 하실 수 있습니다.

 

BFS와 DFS를 stack과 queue를 통해 어떻게 구현하시는지 궁금하신 분들은

https://programmersdiary.tistory.com/76

59. Python 백준 1260 번 DFS와 BFS stack, queue를 이용한 풀이. Stack이란? Queue란? Deque 이란? 파이썬 stack, De

이 예제를 풀어보시고, 제 글의 설명을 읽어보시는 것을 추천드립니다.

 

 

먼저 미로를 그려야 됩니다. 추후에 말이 이동하면서 (x, y 좌표로 표현) 길이 있는지 아닌지 확인하기 위함이죠

from collections import deque
N, M = map(int, input().split())
maze = []

for _ in range(N):
    maze.append(list(map(int, input())))

입력 양식에 맞게 리스트로 입력받습니다.

 

이후 BFS를 구현하기 위해 deque을 선언합니다. queue를 선언해도 됩니다.

deque을 선언해서 queue처럼 사용할 예정입니다.

step = deque() #BFS 를 위해 queue 처럼 사용할 예정

 

시작좌표인 0,0을 삽입해줍니다.

step.append((0, 0))

 

본격적으로 미로찾기 시작입니다.

while step은 (queue가 비어있지 않으면 True, 비어있다면 False입니다.)

step이 비어있지 않다면 while문을 계속 반복합니다.

while step:

step (큐) 안에 들어있는 좌표를 출력해서 방문합니다.

x, y = step.popleft()

 

이후 

(x-1, y) , (x+1, y) , (x, y-1) , (x, y+1) 을 검사합니다. 만약 방문 가능하면 큐에 삽입하고, 거리를 계산해서 삽입합니다.

if (x-1 >= 0) and (maze[x-1][y] == 1): #위쪽 탐색
    step.append((x-1, y))
    maze[x-1][y] = maze[x][y] + 1

if (x+1 < N) and (maze[x+1][y] == 1): #밑쪽 탐색
    step.append((x+1, y))
    maze[x+1][y] = maze[x][y] + 1

if (y-1 >= 0) and (maze[x][y-1] == 1): #왼쪽 탐색
    step.append((x, y-1))
    maze[x][y-1] = maze[x][y] + 1

if (y+1 < M) and (maze[x][y+1] == 1): #오른쪽 탐색
    step.append((x, y+1))
    maze[x][y+1] = maze[x][y] + 1

 

마지막으로 결과값을 출력합니다.

print(maze[N-1][M-1]) #출력

 

 

Python 백준 2178 번 미로 탐색 최종 코드입니다..

from collections import deque
N, M = map(int, input().split())
maze = []

for _ in range(N):
    maze.append(list(map(int, input())))

step = deque() #BFS 를 위해 queue 처럼 사용할 예정
step.append((0, 0))

while step:
    x, y = step.popleft()

    if (x-1 >= 0) and (maze[x-1][y] == 1): #위쪽 탐색
        step.append((x-1, y))
        maze[x-1][y] = maze[x][y] + 1

    if (x+1 < N) and (maze[x+1][y] == 1): #밑쪽 탐색
        step.append((x+1, y))
        maze[x+1][y] = maze[x][y] + 1

    if (y-1 >= 0) and (maze[x][y-1] == 1): #왼쪽 탐색
        step.append((x, y-1))
        maze[x][y-1] = maze[x][y] + 1

    if (y+1 < M) and (maze[x][y+1] == 1): #오른쪽 탐색
        step.append((x, y+1))
        maze[x][y+1] = maze[x][y] + 1

print(maze[N-1][M-1]) #출력

 

Python 백준 2178 번 미로 탐색 이었습니다.

감사합니다.