Problem Solving

[BOJ] 1600 - 말이 되고픈 원숭이

풀이처음엔 DP 문제라고 생각했으나, 부분 문제의 최적의 해가 전체 솔루션의 최적의 해가 될 수 없겠다는 생각이 들었다. 가령 아래와 같은 경우, K = 1이라고 가정해보자. 좌측 상단의 끝점이 [0,0]이라고 가정한다면 [1,2]까지의 최적해는 1이 된다. 0000000011111110 반면 [0,0]부터 [1,2]를 거치고, [3,3]으로 가는 경우는 4가 된다. 그렇지만 이 단계에서의 [1,2]까지의 최적해는 3이다. K를 [0,0] -> [1,2]에 소모한다면 벽을 넘어갈 수 없기 때문이다. 따라서 탐색 문제라는 생각이 들어서 BFS로 해결할 수 없을지 고민했다. 일반적인 완전탐색과 다른 점은 K를 동적으로 사용할 수 있다는 점이다. 말처럼 이동하느냐 마냐에 따라 해당 격자까지의 거리가 달라진다...