백준 알고리즘: 1697번 숨바꼭질

문제 정보

---

 

1697번: 숨바꼭질

 

 

핵심

---

ㅇㅇ

 

풀이

---

처음 풀이(실패) : DFS -> Timeout

DFS 알고리즘을 활용하여 처음 풀이를 시작하였다

하지만 경우의 수가 무수히 많이 나오기 때문에, 전체 경우의 수를 모두 구하기에는 어려움이 있었던 것 같다

아무리 빨리 중단하도록 코드를 작성하여도, 결국에는 특정 조건에 만족하지 않으면 거의 모든 경우의 수를 확인해 봐야만 하기에

이 코드는 이 문제에서 효율적이지 않은 코드였다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static int fastestTime = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int limit = findMinimumValue(N, K);
        DFS(N, K, 0, limit);
        System.out.println(fastestTime);
    }

    public static void DFS(int N, int K, int count, int limit) {
        if (N < 0 || N > 100000)
            return;
        if (count >= fastestTime || count > limit)
            return;
        if (N == K) {
            fastestTime = fastestTime > count ? count : fastestTime;
            return;
        }
        // 2배 했을때도 K보다 작으면 무조건 * 2
        if (N * 2 <= K)
            DFS(N * 2, K, count + 1, limit);
        // K보다 크면 무조건 -1
        else if (N > K)
            DFS(N - 1, K, count + 1, limit);
        // 아닌경우
        else {
            DFS(N * 2, K, count + 1, limit);
            DFS(N + 1, K, count + 1, limit);
            DFS(N - 1, K, count + 1, limit);
        }
    }

    public static int findMinimumValue(int N, int K) {
        int result = 0;
        while (N <= K) {
            N *= 2;
            result++;
        }
        result += Math.abs(K - N);
        return result;
    }
}

 

두번째 코드 : BFS -> Success

BFS 알고리즘을 사용하여 두번째 풀이를 하였다

이 문제에서 왜 BFS를 사용해야 하냐면, 모든 경우의 수를 확인하는 것이 아닌 최단 시간을 확인하는 것이므로

Breath-First-Search 도중에 가장 빨리 나오는 경우가 최단 시간이다

DFS는 한 경로로 쭉 들어갔다가 backtracking을 하며 가지를 탐색하는데, 반면 BFS는

순차적으로 같은 Depth에 있는 요소들을 확인해 나가므로, 가장 빨리 도출되는 Depth가 최단 시간이며 답이다!

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

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int result = BFS(N, K);
        System.out.println(result);
    }

    public static int BFS(int N, int K) {
        int result = 0;
        Queue<Integer> items = new LinkedList<>();
        Queue<Integer> levels = new LinkedList<>();
        boolean[] visited = new boolean[100001];
        items.add(N);
        levels.add(0);
        while (!items.isEmpty()) {
            int item = items.remove();
            int level = levels.remove();
            visited[N] = true;

            // end condition
            if (item == K) {
                result = level;
                break;
            }

            int head1 = item + 1;
            int head2 = item - 1;
            int head3 = item * 2;
            int[] heads = {head1, head2, head3};
            // queue adding
            for (int i = 0; i < 3; i++) {
                if (heads[i] > 100000 || heads[i] < 0 || visited[heads[i]])
                    continue;
                items.add(heads[i]);
                levels.add(level + 1);
                visited[heads[i]] = true;
            }
        }
        return result;
    }
}

여기서 가장 중요했던 것은, visited[] 를 선언하고 방문한 위치는 탐색하지 않도록 해야 하는데

계속 이것을 생각하지 못하고 방황하다가 시간초과가 나서 확인해보니,

+1, -1 등의 연산을 통하여 계속 앞으로갔다 뒤로갔다만 반복하는 쓸데없는 경우의 수가 생기기 때문에

이러한 연산을 visitied 배열을 통해 제거를 해주어야 한다

이걸 하면.. 답이 나올까? 라는 의문이 있었는데 생각해보면,

최단 경로라는 것은 해당 경로의 모든 step에서 최단 경로라는 것이다

5 -> 17까지 가는 경로를 생각해 볼 때

5 -> 10 -> 9 -> 18 -> 17 과 같은 경로가 최단 경로가 되는데, step 1-4까지 이 경로를 탐색하는 동안 해당 위치는 아무도 오지 않았고 내가 처음 온 위치라는 것을 의미한다

(이미 누군가 방문한 사람이 있을수가 없다, 먼저 방문했었다면 그 사람(경로)이 최단 경로가 되어야 하기 때문)

 

 

고찰

---

Backtracking

-> 모든 경우의 수를 확인해 보아야 하는 경우는 DFS를 사용한다

-> 최단 시간이나 최단 level와 같은 느낌인 경우에는 BFS를 사용한다

이 경우에는 반드시 visited 배열을 사용해서, 방문한 노드는 더이상 방문하지 못하도록 처리해 주어야 함을 꼭 인지하기!

 

Source Code on GitHub

---