[BOJ] 백준 1697 숨바 꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제

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

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

풀이

• 수빈이가 1초 동안 이동할 수 있는 경우 3가지 (-1, 1, x 2배)를 dx배열에 선언한다.
• 수빈이가 움직인 곳을 checked배열에 표시한다.
• 수빈이가 최초로 방문한곳(방문하지 않았던 곳)은 checked배열의 이전 방문 위치의 시간 + 1만큼 넣어 준다.
• 방문하지 않았던 곳은 checked배열에 표시하면서 , 큐에 넣어준다. 
• next(다음 위치가) 목표 지점과 같을 때까지 계속 위치를 체크하고 방문하지 않았으면 큐에 넣는 작업을 반복한다.

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 Problem_1697_somba {

    static int[] dx = {-1, 2, 1};
    static int[] checked = new int[100001];
    static int I;
    static int J;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        I = Integer.parseInt(st.nextToken());
        J = Integer.parseInt(st.nextToken());

        if (I == J) {
            System.out.println(0); // 예외 케이스
        } else {
            BFS(I);
        }
    }

    private static void BFS(int i) {

        Queue<Integer> queue = new LinkedList();
        queue.offer(i);
        checked[i] = 1;

        while (!queue.isEmpty()) {
            int tempx = queue.poll();
            for (int k = 0; k < 3; k++) {
                int next;

                if (k == 1) {
                    next = tempx * dx[k];
                } else {
                    next = tempx + dx[k];
                }

                if (next == J) {
                    System.out.println(checked[tempx]);
                    return;
                } else if (next >= 0 && next <= 100000 && checked[next] == 0) {
                    queue.offer(next);
                    checked[next] = checked[tempx] + 1;
                }
            }
        }
    }
}

다른풀이

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] check = new boolean[MAX];
        int[] dist = new int[MAX];
        check[n] = true;
        dist[n] = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(n);
        while (!q.isEmpty()) {
            int now = q.remove();
            if (now-1 >= 0) {
                if (check[now-1] == false) {
                    q.add(now-1);
                    check[now-1] = true;
                    dist[now-1] = dist[now] + 1;
                }
            }
            if (now+1 < MAX) {
                if (check[now+1] == false) {
                    q.add(now+1);
                    check[now+1] = true;
                    dist[now+1] = dist[now] + 1;
                }
            }
            if (now*2 < MAX) {
                if (check[now*2] == false) {
                    q.add(now*2);
                    check[now*2] = true;
                    dist[now*2] = dist[now] + 1;
                }
            }
        }
        System.out.println(dist[m]);
    }
}