BOJ01697 숨바꼭질

https://www.acmicpc.net/problem/1697 (opens new window)

수빈이는 현재 점 N(0 <= N <= 100,000)에 있고, 동생은 점 K(0 <= K <= 100,000)에 있다. 수빈이는 걷거나 순간이동이 가능하다.

1. 수빈이의 위치가 X일 때 걷는다면 1초 후 X - 1, X + 1로 이동이 가능하다.
2. 수빈이의 위치가 X일 때 순간이동 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다.

BFS 활용

BFS는 너비 우선 탐색이라는 의미를 가진다. 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현은 선입선출 방식은 큐 자료구조를 이용한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

아래는 실제 사용하는 bfs 메소드를 구현한 것이다.

현재 점 n을 기준으로 queue에 삽입한 후 진행한다. count의 경우 방문 처리 + 방문 횟수를 저장하기 위한 용도이다.

Queue<Integer> queue = new LinkedList<>();
queue.add(n);
count[n]++;

좌표를 이동하는 방법은 크게 3가지 이다. 모든 경우를 반복하여 탐색한다.

if (i == 0) {
    next = poll - 1;
} else if (i == 1) {
    next = poll + 1;
} else {
    next = poll * 2;
}

탐색 중 k에 도달하면 방문 횟수를 반환한다.

if (k == next) {
    return count[poll];
}

현재 방문한 좌표가 유효한 좌표(방문하지 않은 좌표)이면 queue에 저장하고 방문 횟수를 증가 시킨다.

if (next >= 0 && next < count.length && count[next] == 0) {
    queue.add(next);
    count[next] += count[poll] + 1;
}

아래는 최종 bfs 메소드이다.

private static int bfs() {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(n);
    count[n]++;

    while (!queue.isEmpty()) {
        Integer poll = queue.poll();
        for (int i = 0; i < 3; i++) {
            int next;
            if (i == 0) {
                next = poll - 1;
            } else if (i == 1) {
                next = poll + 1;
            } else {
                next = poll * 2;
            }

            if (k == next) {
                return count[poll];
            }

            if (next >= 0 && next < count.length && count[next] == 0) {
                queue.add(next);
                count[next] += count[poll] + 1;
            }
        }
    }

    return 0;
}

제출 코드

위에서 작성한 bfs 메소드를 기반으로 최종 제출한 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ1697 {

    static int n, k;
    static int[] count = new int[100_001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt(); // 수빈이의 현재점
        k = scanner.nextInt(); // 동생의 현재점

        if (n == k) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static int bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        count[n]++;

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) {
                    next = poll - 1;
                } else if (i == 1) {
                    next = poll + 1;
                } else {
                    next = poll * 2;
                }

                if (k == next) {
                    return count[poll];
                }

                if (next >= 0 && next < count.length && count[next] == 0) {
                    queue.add(next);
                    count[next] += count[poll] + 1;
                }
            }
        }

        return 0;
    }
}

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색