<SWEA> 최솟값으로 이동하기

풀이

문제를 읽고 W와 H의 범위를 보고 DFS로는 불가능할 거같은데.. 라는데 생각이 들긴 하였다. 하지만 일단 다른 방법이 딱히 떠오르지 않아 DFS를 이용하여 풀이를 시작하였다. 2차원 배열 map을 만들고 순서대로 좌표를 입력받으면서 1부터 1씩증가하며 2,3,...이런식으로 채워넣었다.

 

DFS탐색을 시작하면서 현재값은 1로 두고 2인 좌표에 도착하면 다음 목표를 3으로 바꾸고 3에 도착하면 4로 바꾸는 식으로 코딩을 하였다. 결과적으로 시간 초과에 걸렸다. 여기서 가지치기를 해보자는 생각이 들어서 한번씩 진행할때마다 cnt가 증가하는데 최소이동거리 min보다 더 많으면 그건 이미 이전에 구한 예비 정답보다 더 느리므로 return을 하는식으로 수정하였다. 결과적으로 똑같이 시간 초과가 발생하였다. 

 

고민을하다 결국 재귀도 아니고 그냥 현재좌표에서 다음 좌표로 가는 방법이 빠르다는 것을 알게 되었다. 다른 분들의 블로그를 참고한 결과 현재좌표와 다음좌표간의 x좌표 차이와 y좌표 차이의 곱이 양수이면 지름길로 이동가능하다.

이를 이용해 코딩하였다.

 

코드