[Python] BOJ(백준) 2178번 - 미로 탐색

링크

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

난이도(solved.ac 참고)

실버1

풀이

이 문제를 왜 지금까지 안 풀었었는지 모르겠다. BFS(DFS도 쓸 수 있긴 함)의 너무 기본적인 문제라 쓰기도 좀 애매하긴 한데..

 

값을 받아오고 각 위치별로 방문 여부를 확인하는 visited 배열을 선언해준다. 그다음 0, 0 위치에서 BFS 함수를 시작하면서

1) nx와 ny가 미로를 벗어났는지 확인

2) (nx,ny) 좌표를 이미 방문했는지 여부를 확인

3) 1, 2 모두 충족했을 경우 해당 좌표가 벽인지 확인(0이면 벽, 1이어야 지나갈 수 있는 길임)

이 경우 방문처리를 하고 큐에 지금까지 이동한 값인 distance에 1을 더한 값을 넣는다. 시작점도 거리에 포함한다고 했으므로 초기에 들어가는 값은 1이다.

좌표가 (n-1, m-1)이 되었을 때 그 위치로 오기까지의 거리인 distance를 출력해준다.