[JAVA] 백준 (실버1) 1697번 숨바꼭질

링크

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

---

문제 설명

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

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

---

입력 예제

5 17

---

출력 예제

4 (수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.)

---

정답 코드

목표 지점까지 최소 이동 횟수를 구해야 하므로 BFS를 이용한다.

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

public class Main {

    static int[] pos = new int[100001]; //좌표 배열
    static boolean[] visit = new boolean[100001]; //방문 체크 배열

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        bfs(N);
        System.out.println(pos[K]);
    }

    //너비 우선 탐색 메서드
    static void bfs(int N) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        visit[N] = true;
        int nextPos = 0;
        //큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            //큐의 첫번째 원소를 뽑아 현재 위치로 할당
            int curPos = queue.poll();
            //3가지 경우의 수에 따라 반복
            for (int i = 0; i < 3; i++) {
                //X + 1로 이동
                if (i == 0) {
                    nextPos = curPos + 1;
                }
                //X - 1로 이동
                if (i == 1) {
                    nextPos = curPos - 1;
                }
                //2 * X로 이동
                if (i == 2) {
                    nextPos = curPos * 2;
                }
                //배열을 벗어날 경우
                if (nextPos < 0 || nextPos >= 100001) {
                    continue;
                }
                //방문하지 않은 곳일 경우
                if (!visit[nextPos]) {
                    queue.add(nextPos);
                    visit[nextPos] = true;
                    pos[nextPos] = pos[curPos] + 1; //좌표 갱신
                }

            }

        }
    }
}

---

정리

이전에 푼 미로 탐색처럼 현 좌표값을 갱신해간다.
처음 본 유형이였으면 어려웠겠으나 BFS도 풀다보니 익숙해 지는거 같다.