[Java] 백준 BOJ / 13549번: 숨바꼭질 3

숨바꼭질 3

문제

문제 설명

한 수직선 상 위에 수빈이의 위치 N과 동생이 있는 위치 K가 주어지고 수빈이의 위치가 X때 이동가능한 곳은 X-1, X+1, 2X가 가능하다고 할 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.

이 문제는 BFS로 접근하면 풀 수 있다.

일단 Point 클래스를 아래와 같이 선언하고 현재의 위치와 경과된 시간을 저장할 수 있는 index 변수와 time변수를 사용했다.

public static class Point {
	int index;
	int time;

	public Point(int index, int time) {
		this.index = index;
		this.time = time;
	}
}

이렇게 선언한 후에 평범한 BFS처럼 풀면 되는데 BFS에서 사용되는 큐에 넣을 때 문제의 조건에 맞게 순간이동을 했을 때, 한걸음 앞으로 갔을 때, 한걸음 뒤로 갔을 때를 비교해주고 만약에 동생의 위치인 K에 도착을 했다면 결과를 비교해서 최소를 구해주면 끝나는 문제이다.

여기서 주의할 점은 연산 순서인데 순간이동을 하는 것이 더 시간적으로 이득이기 때문에 순간이동의 순서를 가장 앞에서 해주어야 한다.

코드

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

public class Main_13549 {
    static int n, k;
    static boolean[] visited;
    static int result = Integer.MAX_VALUE;
    static int MAX = 100000;

    public static class Point {
        int index;
        int time;

        public Point(int index, int time) {
            this.index = index;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        visited = new boolean[1000001];
        bfs();
        System.out.println(result);
    }

    public static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(n, 0));

        while (!q.isEmpty()) {
            Point point = q.poll();
            visited[point.index] = true;
            if (point.index == k) {
                result = Math.min(result, point.time);
            }

            if (point.index * 2 <= MAX && !visited[point.index * 2]) {
                q.offer(new Point(point.index * 2, point.time));
            }
            if (point.index + 1 <= MAX && !visited[point.index + 1]) {
                q.offer(new Point(point.index + 1, point.time + 1));
            }
            if (point.index - 1 >= 0 && !visited[point.index - 1]) {
                q.offer(new Point(point.index - 1, point.time + 1));
            }
        }
    }
}