[Python] 미로 찾기(BFS)

문제 기술

m×n 크기(m은 행의 개수, n은 열의 개수)의 배열로 표현되는 미로가 있다. 1은 갈 수 있는 곳을 나타내고, 0은 갈 수 없는 곳을 나타낸다.

미로의 가장 위에서 가장 아래로 내려가는 최단 경로의 길이 (지나는 1의 개수)를 구하는 프로그램을 작성하시오. 미로의 각 위치에서 상하좌우로 인접한 곳으로만 갈 수 있다. 가는 길이 없으면 -1을 출력한다.

 

입력

6 10  // m n은 각각 2이상 100이하 정수
0110000011
1101111101
1101010111
1111010111
0100111000
1011110111

출력

 12

나의 코드

0부터 3까지 i에 대한 for문을 돌리면서 동서남북으로 좌표 이동을 했고,

미로 밖으로 안나갔을 경우, 그리고 아직 방문하지 않았을 경우 해당하는 곳의 값이 1인 경우에 

#1: 방문처리를 하고

#2: 그 지점까지의 거리를 기존 위치까지의 거리 + 1로 설정했다.

그다음, y좌표가 m-1, 즉 맨 아랫줄에 위치하게 되었을 경우 큐를 비워주고 distance 값을 리턴했다.

 

38~40행은, map의 첫 시작점이 1이 되는 경우에 한해서만 bfs 함수를 진행하도록 했다.

메인 함수의 경우 m-1에 도달하지 못하는 경우에는 None을 리턴하게 된다. 그래서, 41행의 res를 통해 None을 전부다 지워줬다.

그리고, 지워준 res의 길이가 0이라면 그곳은 결국 갈 수 없는 것이므로 -1을 리턴하였고, 그게 아닌 경우 for문을 다 돌고 난 뒤에 res에 들어가 있는 리스트의 값들 중 가장 작은 값, 그러니까 우리가 구해야 하는 최소 경로를 출력하게 하였다.

코드는 여기에 있다.