백준 알고리즘 - 미로 탐색 (2178) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

 

 

 

 

 문제 상황

 

- 시작점에서 끝점까지의 길이 항상 존재할 때 가장 최단으로 갈 수 있는 거리의 길이를 찾는다.

 

 

 

 

 

 

 

 해결 전략

 

- 최단거리이므로 BFS를 활용하여 deque를 이용한다.

 

 

 

 

 

 

 

 코드

 

from sys import stdin
from collections import deque
input = stdin.readline
N, M = map(int, input().split())
maze = [list(map(int, list(input().strip()))) for _ in range(N)]
visiting = deque([(0,0)])
visited = [[False for i in range(M)] for j in range(N)]
dx, dy = [0,0,-1,1], [1,-1,0,0]
while visiting:
    x, y = visiting.popleft()
    visited[x][y] = True
    for i in range(4):
        xx, yy = x+dx[i], y+dy[i]
        if 0<=xx<N and 0<=yy<M:
            if maze[xx][yy] == 1 and visited[xx][yy] == False:
                visiting.append((xx,yy))
                maze[xx][yy] += maze[x][y]
print(maze[N-1][M-1])

 

 

 

 

 

 

 

 

 해설

 

- 4방향을 체크하여 방문하지 않은 곳 중 진입 가능하면 현재 위치의 거리와 1을 더해준다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 최단거리를 구할 때에는 BFS를 사용하고, 한번 방문했다는 의미는 이미 최단 경로로 도착했다는 뜻이다. 왜냐하면 BFS는 같은 깊이를 무조건 먼저 방문하고 더 깊은 곳을 나중에 방문하기 때문이다.