백준 1697번 숨바꼭질 :: 마이구미

이번 글은 백준 알고리즘 문제 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

static int n;
static int k;
static int[] dx = { -1, 1, 0 };
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 (0 <= 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;
    }
}