2178 미로탐색

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

2178번: 미로 탐색

- 미로의 시작 [0,0] 에서 [n-1, m-1]로 빠져나가는 최단거리를 구하는 문제

- 정점간의 거리가 모두 1 이므로 BFS를 사용하여 최단거리를 구할 수 있다.

 

1. 탐색중인 위치(x,y) 를 표시할 클래스 Pos를 만들었다.
2. 반복문을 이용해 이동가능한 상하좌우 좌표를 확인하기 위해 상하좌우로 이동시켜줄  _x, _y 배열을 생성했다.
   1. 즉 각각의 배열 인덱스 0은 '상' 으로 이동하기 위한 x좌표, y좌표를 담고 있다.
   2.  위와 같은 방식으로 상하좌우를 표시하고, 순서는 상관없다.
3. 이동할 때 마다 직전위치에서 이동거리(ans[x][y]) 에 +1을 하여 ans[nx][ny]에 저장한다.
   1. ans[0][0]은 시작위치 이므로 1
   2. ans[1][1]은 한칸 이동했으므로 1+1 = 2
   3. 최종적으로 ans[n-1][m-1] 에는 최단거리가 들어가게 된다.

 

- 헷갈렸던 점 : 

BFS는 동시에 이동가능한 정점을 모두 방문하는데, 다음과 같은 경우 최단거리가 나올 수 없게되는 것 아닐까? 라는 생각을 했음

파란색선은 17블럭, 빨간색선은 15블럭을 이동한다. 파란색선이 더 늦게 도착하니까 ans[n-1][m-1]을 덮어쓰는게 아닐까 라는 걱정을 했지만

 

이동할때 마다 visit에 방문한 정점을 체크하고 있으니, 파란색선처럼 돌아서 가는 경우 if( !visit[3][1] )을 통과하지를 못함. 그래서 결국 최단거리만 ans배열에 저장됌.