[항해99 취업 리부트 코스 학습일지] 알고리즘 문제풀이

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

문제

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

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

---

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

---

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

풀이

목표 지점까지의 최단 경로를 구하는 문제로 전형적인 BFS 문제이다.
-1지점, +1지점, *2 지점에 이동 횟수를 기록한다.
목표 지점에 다다를때까지 이동 횟수를 기록하고 목표 지점에 기록된 횟수를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/*
이동 횟수 기록할 최대 입력값 크기의 배열 생성
시작 지점 1부터
bfs
-1, +1, *2 지점 이동 횟수 기록
 */
public class Main {
    public static void main(String[] args) throws IOException {
        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());

        //최대 입력값
        int[] index = new int[100_001];

        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        // 1부터 시작
        index[n] = 1;

        while (!q.isEmpty()) {
            Integer x = q.poll();

            // +1 지점
            int nx = x + 1;
            if (0 <= nx && nx < 100_001) {
                // 이동 횟수가 아직 기록되지 않았으면(아직 방문하지 않았으면)
                if (index[nx] == 0) {
                    q.add(nx);
                    index[nx] = index[x] + 1;
                }
            }

            // -1 지점
            nx = x - 1;
            if (0 <= nx && nx < 100_001) {
                if (index[nx] == 0) {
                    q.add(nx);
                    index[nx] = index[x] + 1;
                }
            }

            // *2 지점
            nx = x * 2;
            if (0 <= nx && nx < 100_001) {
                if (index[nx] == 0) {
                    q.add(nx);
                    index[nx] = index[x] + 1;
                }
            }
        }

        // 1부터 시작했으니 1빼고 출력
        System.out.println(index[k] - 1);
    }
}

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.