[백준 2178] 미로 탐색(python)

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

2178번: 미로 탐색

미로 탐색 문제

미로를 탐색해 나갔을 때, 도착 지점에 도착할 경우 총 몇 칸을 이동하게 되는지 구하는 문제

BFS를 활용하면 간단하게 풀 수 있는 문제

내가 푼 정답코드

def finding(a,b): #길을 찾아주자
    visited = [[0]* M for _ in range(N)]
    queue = [[a,b]]
    visited[a][b] = 1 # 방문 처리
    while queue:
        y, x = queue.pop(0)
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == 0 and maze[ny][nx] != 0:
                visited[ny][nx] = visited[y][x] + 1 # 출발지부터 이동한 거리재기
                queue.append([ny,nx])
    return visited[N-1][M-1] #도착점 도착했을 때 거리

import sys
N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0],[-1,0],[0,1],[0,-1]]
print(finding(0,0)) #출발 지점

가장 기본이 되는 BFS를 이용한 미로를 탐색하는 문제이다.

접근 법은  BFS를 구현해주고, 다음칸이 이동할 수 있는 인접 칸이면 다음칸에 현재칸 +1한 만큼 이어 나가면 도착 지점에 도착할 때까지 이동한 거리를 알 수 있다.

---

느낀 점

BFS를 활용한 미로 탐색의 가장 기본이 되는 문제이다. 이전에 미로 탐색 문제를 여러번 풀어봐서 큰 어려움 없이 풀 수 있었다.