[백준/Baekjoon 2178] 미로탐색 파이썬(Python) 풀이

문제

백준 2178 미로문제

문제 핵심

-> 문제를 해결하는데 있어서 중요한 부분은 미로에서 1일 때만 이동이 가능하고 (1,1)에서 출발해 (N,M)까지 이동할 때 지나야하는 최소의 칸 수를 구해야한다. 여기서 입력을 배열형태로 입력을 받을 경우 (0,0)에서 (N-1,M-1)까지로 받아야한다.

 

그림으로 보기

 

 1인 부분을 지나가야하는 문제에서 DFS 또는 BFS를 고민할 수 있다. 

사람마다 자신이 자신있는 것을 선택해서 풀면 되지만 

좌표가 나오는 DFS,BFS 문제의 경우 BFS로 푸는것이 더 편하다

 

위의 그림을 보면 1을 지나갈 때마다 전 방문 칸수 +1를 해준다.

빨간색의 숫자가 지금까지 방문한 칸수가 되는 것이다.)

(문제 풀때 위의 입력되어있는 '1' 부분이 DFS함수를 돌면 지금까지 지나온 칸 수로 저장한다고 보면 편하다)

 

풀이과정

1. N, M을 입력을 받는다.

2. 좌표이동 문제임으로 dx, dy를 설정한다.

3. 미로탐색 miro 리스트 선언 후 for 문을 통해 미로를 입력 받는다.

4. BFS를 사용하기위한 방문 리스트 visitied 를 만든다.

5. BFS함수 선언한다.

BFS 함수
1) deque로 queue를 선언
2) queue에 좌표를 append한다.
3) visitied 리스트에 방문표시를 한다.
4)  while queue 작성 -> x,y 이동하는 식을만든다.
5) return문은 위의 그림설명 괄호부분이면 된다. 

정답코드

from collections import deque
def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visitied[x][y] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and miro[nx][ny] == 1:
                queue.append((nx, ny))
                miro[nx][ny] = miro[x][y] + 1
    return miro[N - 1][M - 1]
N, M = map(int, input().split())
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
miro = []
for i in range(N):
    miro.append(list(map(int, input())))
visitied = [[False] * (M) for i in range(N)]  # 방문했는지 확인하는 배열
print(BFS(0, 0))