BOJ 1600 말이 되고픈 원숭이

yukariko(유카리코)님의 코드와 방식을 거의 그대로 사용하여 풀었다.

이 문제를 풀면서 다시금 내가 bfs에 대한 이해가 부족하다는 것을 느꼈다.
유카리코님의 코드를 보면 정말 bfs를 꿰뚫고 있어야 저런 코드를 짤 수 있구나 하는 것을 느낀다. 정말 멋있는 방법이었다.

그리고 같이 공부하는 wonsik의 아이디어도 시간 단축에 큰 몫을 했다. 바로 왼쪽 위 부분의 2방향은 볼 필요가 없다는 것이다. 왼쪽 위에서 오른쪽 아래로 가는 것이므로 또한 최소 횟수를 구하는 것이므로...(물론 확실히 증명하거나 한 건 아니지만...음) 일단, 목표지점이 맨 오른쪽 맨 아래 이기도 하고, 어떤 위치에서 저 두가지 방향을 써서 돌아갔다가 목표지점 까지 가는 것보다 그 위치에서 바로 목표지점까지 가는 것이 나을 것이고...음 생각을 해봐야겠지만... 일단은 그래보인다.

(2년 뒤에 보니... 재채점이 되어있었고, 내가 제출한 상당수의 코드가 AC에서 WA로 바뀌어 있었다... 아마도 왼쪽 위의 2방향을 볼 필요가 없다고 처리해서 그런 것 같다. 사실 생각해보면 왼쪽 위의 2방향도 봐야하는 경우가 있을 수도 있을 것 같다. 돌로 막혀 있어서, 왼쪽 위로 갔다가 나와야 하는 그런... 앞으로 증명하지 않고 추측으로만 코드를 짜는건 자제해야겠다. 실제로 그 부분만 고쳐서 내보니 )

이제 유카리코님의 아이디어를 보면, 여기서 구하는 답인 원숭이가 움직인 횟수는 결국, bfs를 쓰기 때문에 처음으로 방문한 곳이 최소의 동작횟수를 써서 방문한 것이 되는 것이고, 그 동작횟수라 함은 bfs의 단계의 개수로 볼 수 있다.

그래서 목적지가 처음 나오기 전까지, bfs의 단계가 몇단계인지 세주는 것이다...!

유카리코님의 아름다운 코드 였다.