백준 1697 - 숨바꼭질

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

DP 문제같아 보이는데 DP로는 풀기 어렵다고 한다. 그렇다고 왜 BFS로 풀어야 하는지도 처음에는 납득이 되지 않았다.

어찌됐건 1차원 배열의 BFS를 통해 답을 쉽게 찾을 수 있다. BFS를 수행하면서, 사용된 이동 방식 (X-1, X+1, X*2)을 별도의 배열 path에 저장하고 탐색이 끝나면 k에서부터 경로를 역추적하면 된다.

 

path에 저장하는 값을 아래와 같이 설정하면, 경로 추적 함수를 재귀적으로 간단하게 작성할 수 있다!

BFS(...) {
...
//X-1
path[next_pos] = -1;

//X+1
path[next_pos] = 1;

//X*2
path[next_pos] = cur_pos;
...
}

int findPath(int n, int k, int count) { //k에서 출발해 n까지 이동
    if (n == k)
        return count;
    findPath(n, k - path[k], count + 1);
}

* BFS를 사용하는 이유 (추측)

 

왜 DP는 안되는가?

n <= k라는 보장이 없어 만약 n > k일 경우 계산이 복잡해지기 때문이다.

 

왜 DFS는 안되는가?

X-1, X+1에서 대부분의 경우 바로 이동해버리기 때문에, X*2 연산이 거의 시행되지 않아 최단 경로를 찾기 어렵기 때문이다.