BOJ 1697) 숨바꼭질

 

1.

 처음 문제를 보니깐 dp로 풀면 될 것 같아서 먼저 dp로 풀어보았다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        int[] arr = new int[100001]; //0~100000
        for(int i=0; i<100001; i++)
            arr[i] = 100001; //최소비교를 위해 대충 큰값
        for(int i=N-1; i>=0; i--)
            arr[i] = N-i;
        arr[N]=0;
        if(N<K) {
            for(int i=N+1; i<100000; i++) {
                if(i%2==0)
                    arr[i] = Math.min(arr[i/2], Math.min(arr[i-1], arr[i+1]))+1;
                else
                    arr[i] = Math.min(arr[i-1], arr[i+1])+1;
            }
            arr[100000] = Math.min(arr[50000], arr[99999]);
        }
        System.out.println(arr[K]);

    }
}

처음에는 이렇게 코드를 작성했다. arr[i]란 N에서 K까지 가는 도중에 걸리는 최단 이동 횟수를 나타낸다. 일단 N>K라면 무조건 1씩 감소시켜가며 접근하는 방법밖에 없기 때문에 arr[0]~arr[N-1]까지는 N-i의 값을 갖고, arr[N]=0이다.

그런데 생각보다 로직의 반례가 다수 존재한다는 것을 깨달을 때쯤 구글링을 해봤고, 다음과 같은 글을 보게 되었다.

 

https://www.acmicpc.net/board/view/41340

"이 문제와 같이 DAG가 아닌 그래프에서 특정 방향을 정해 놓고 dp를 하는 것은 매우 위험합니다. 그렇게 하는 것이 옳다는 증명을 할 수 없다면, 옳지 않을 가능성이 높습니다."

참고) DAG란? 간단하게 방향성이 존재하고 사이클이 없는 그래프. (https://jeonyeohun.tistory.com/99)

 

 

문제의 조건대로 단순하게 짝수조건만 확인하고 Math.min으로 최소값을 구해나갔는데, 위 문제는 방향성을 가지고 있지 않다. "1초 후에 X-1로 이동할 수도 있다"는 조건이 그래프가 방향성을 갖지 않게 만든다고 생각했다. i번째 배열 인덱스에서 i+j번째 배열 인덱스로 갈 때, i와 i+j 사이에 어떤 인덱스를 거치지 않고, i-1을 임의의 횟수만큼 반복한 후에 갈지도 모른다는 것.

 

위 코드는 i가 작은 수부터 큰 수까지 방향성을 갖고 DP가 진행되게 구성되었다. 물론

Math.min(arr[i-1], arr[i+1])+1;

과 같이 arr[i-1]이 고려된 것처럼 보이지만, 진행 방향이 작은 수에서 큰 수인 만큼, 진행 방향에 따라 체크되지 못한 값들도 존재할 수 있기 때문에 틀린 풀이였던 것이다. 찝찝해도 dp로 되겠지~라고 생각하면서 풀었는데, 그러지 말자.

 

 

2. 그래서 그 다음으로 생각한 방법이 bfs이다. 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        Element e = new Element(N, 0);

        Queue<Element> queue = new LinkedList<>();
        queue.add(e);
        while(!queue.isEmpty()) {
            Element target = queue.remove();
            if(target.number==K) {
                System.out.println(target.depth);
                return;
            }
            else {
                e = new Element(target.number-1, target.depth+1);
                queue.add(e);
                e = new Element(target.number+1, target.depth+1);
                queue.add(e);
                e = new Element(2*target.number, target.depth+1);
                queue.add(e);
            }
        }

    }
}

class Element {
    int number;
    int depth;

    public Element(int number, int depth) {
        this.number = number;
        this.depth = depth;
    }
}

 큐를 이용하기 위해서 현재 위치와 탐색의 깊이정보를 담은 Element라는 클래스를 만들었다. 예전에 좌표상에서 bfs/dfs하는 문제에서 Location이라는 클래스를 만들어서 해결한 경험이 있어서 이렇게 했는데, 문제는 이렇게 일반적인 BFS 탐색방법만 사용하게 되면 시간초과가 발생한다. bfs의 특성상 현재 level의 모든 경우의 수를 확인하는데, 이 경우 i-1, i+1, i*2의 세 경우를 모두 확인하기 때문에 탐색해야 하는 branch의 개수가 3^depth만큼 늘어나기 때문이다.

 

 

 

 따라서 시간복잡도를 줄이기 위해 1차원 배열을 사용하여 큐에 값을 저장함과 동시에 최소 접근시간을 갱신해주었다. 이 때 핵심은 BFS를 이용하므로 처음 접근이 이루어지는 시간이 최소 접근 시간이라는 것. 즉 한번 값이 갱신된 1차원 배열의 값은 더 이상 갱신이 필요없다.

(arr[i] : 위치 N에서 위치 i로 접근할 때 걸리는 최소 접근 시간. 우리가 구하고자 하는 값은 arr[K]이다.)

 

따라서 초기값 N을 큐에 넣고, arr[N]=0으로 초기 시간을 설정해 준 다음, 큐를 돌려가면서 초기화되지 않은 인덱스에 접근하는 경우만 다음 탐색을 진행(큐에 넣기)하면 최소 시간에 원하는 인덱스까지의 접근 시간을 구하면 된다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int[] arr = new int[100001]; // 0~100000
//        for (int i : arr) { //iter문은 Collection에서만 사용가능한것같다..
//            arr[i] = -1;
//        }
        for(int i=0; i<100001; i++)
            arr[i] = -1; //초기화되지 않은 상태 설정

        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        arr[N] = 0; //arr[N] 최기값은 내가 설정해주어야 한다.
        while(!queue.isEmpty()) {
            int target = queue.remove();
            if(target==K) {
                System.out.println(arr[target]); //정답(arr[K])을 구한 경우 종료
                return;
            }
            else { //arr[]에 최초 접근하는 경우만 다음 탐색을 진행한다.
                if(target>=1 && arr[target-1]==-1) {
                    queue.add(target-1);
                    arr[target-1] = arr[target]+1;
                }
                if(target<100000 && arr[target+1]==-1) {
                    queue.add(target+1);
                    arr[target+1] = arr[target]+1;
                }
                if(target<=50000 && arr[2*target]==-1) {
                    queue.add(2*target);
                    arr[2*target] = arr[target]+1;
                }
            }
        }
    }
}

 

 

 꽤 익숙해졌다고 생각하는 탐색 문제인데.. 정말 오래걸렸고 결국 최종 아이디어도 구글링을 통해서 얻었다.

 dp는 옳은 방법이 아니라는 것을 알지 못해서 헤맨 것을 제외하더라도,  문제 조건자체가 단순히 탐색을 해나가는 것이 아니라, 깊이를 구해야 된다니깐 거기서 많이 헤맸다. (깊이를 어떻게 저장하지? HashMap써야되나??) 막상 알고보니 어렵지 않은 발상이라고 생각하는데, 나는 기존에 사용했던 '클래스 큐(?)' 의 방법밖에 생각나지 않았음. 하지만 이 방법으로는 시간초과가 나서 새로운 방법을 생각해야 했다.

 또 문제를 전혀 이해하지 못했고, 적용하지 못했다. bfs의 특성상 depth가 time을 의미하고, 따라서 일단 접근시간이 처음 구해지면 그 값이 최소라는 생각을 하지 못함. dp처럼 갱신하면서 최소값을 찾을 생각도 해서 Math.min으로 비교하려고 하기도 했다.

 

  질문이 간단해보이는 문제더라도, 머리속에서 풀이방법이 꼬이는 경우가 많은 것 같다. 문제에 접근하는 정도가 많아지면 괜찮아질수도 있겠지만, 실제 코테에서 적용하려면 시간이 많지 않기 때문에 한문제 풀 때 확실하게 기억해두도록 노력하자.