• 백준 1697번 숨바꼭질 :: 마이구미
    알고리즘 풀이/그래프 2017. 7. 23. 17:15
    반응형

    이번 글은 백준 알고리즘 문제 1697번 "숨바꼭질" 을 다뤄본다.

    문제 접근 방법은 BFS를 통해 해결했다.

    DFS, BFS - http://mygumi.tistory.com/102

    Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc


    수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

    수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.


    단순하게 DFS와 BFS 중 어떤 것을 선택해야할 경우에 대해 잘 보여주는 문제라고 생각한다.

    본인은 처음에는 DFS를 통해 접근했다.

    DFS를 통해 깊게 탐색할 경우, DFS의 단점인 트리의 깊이가 길 경우에 나오는 문제점들이 고스란히 보여졌다.

    그 결과, 스택오버플로우를 경험하게 되어 BFS로 바꾸게 되었다.

    물론, DFS로도 풀 수는 있지만, 이러한 문제는 BFS를 이용하는 것이 더욱 효율적이다.


    BFS의 탐색 특성상 모든 분기점을 큐를 이용하여 레벨순으로 탐색하기 때문에, 목표 지점이 도달하는 순간이 최소 시간이 된다.


    그렇기에, 큐에 삽입할 때, x-1, x+1, x*2 세가지 경우와 그 시점에 대한 시간을 함께 넣어주면서, BFS를 탐색하면 된다.

    시간의 경우는 배열을 이용하는 방법과, class를 이용하는 방법이 있다. (본인은 class)


    5014번 스타트링크 문제도 거의 흡사하다.

    문제 - https://www.acmicpc.net/problem/5014

    풀이 - http://mygumi.tistory.com/187


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    static int n;
    static int k;
    static int[] dx = { -11};
    static boolean[] visited = new boolean[100001];
     
    private void solve() {
        n = sc.nextInt();
        k = sc.nextInt();
     
        if (n >= k) {
            System.out.println(n - k);
            return;
        }
     
        System.out.println(bfs(n));
    }
     
    public static int bfs(int v) {
        Queue<Node> q = new LinkedList<>();
     
        visited[v] = true;
        q.add(new Node(0, v));
     
        while (!q.isEmpty()) {
            Node node = q.poll();
            int cnt = node.count;
            int pos = node.value;
     
            if (pos == k) {
                return cnt;
            }
     
            for (int i = 0; i < 3; i++) {
                int next;
     
                if (dx[i] != 0) {
                    next = pos + dx[i];
                } else {
                    next = pos * 2;
                }
     
                if (<= next && next <= 100000) {
                    if (!visited[next]) {
                        q.add(new Node(cnt + 1, next));
                        visited[next] = true;
                    }
                }
     
            }
     
        }
     
        return 0;
    }
     
    public static class Node {
        int count;
        int value;
     
        Node (int count, int value) {
            this.count = count;
            this.value = value;
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.