• 문제: https://www.acmicpc.net/problem/1697

설명

이러한 방식으로 탐색하면서 N이 K와 같은 상황을 찾는다.

• 방문할 곳들을 queue에 넣고 하나씩 꺼내어, 방문한다.
  • 범위 안에 있고 이전에 방문한 이력이 없다면 큐에 넣는다.
• 이미 방문한 곳과 방문 횟수를 관리하기 위한 visited 배열을 생성한다.
  • 방문했던 숫자를 체크하기 위해 배열의 크기는 100,001개로 초기화한다.
  • 최소 시간을 기록하기 위해 이전 위치에서 시간 + 1을 하여 관리한다.
• N과 K가 같다면, 이동 횟수는 0임을 지정한다.

코드

package Algorithm.P1697;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P1697 {
    static int N, K;
    static Queue<Integer> queue;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P1697/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        queue = new LinkedList<>();
        visited = new int[100001];

        queue.add(N);

        if (N == K) {
            System.out.println("0");
        } else {
            bfs(N);
        }
    }

    private static void bfs(int n) {
        queue.add(n);
        visited[n] = 1; // 방문 표시
        while (!queue.isEmpty()) {
            int temp = queue.poll();    // 값을 빼낸다.
            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) {
                    next = temp - 1;
                } else if (i == 1) {
                    next = temp + 1;
                } else {
                    next = temp * 2;
                }
                if (next == K) {
                    System.out.println(visited[temp]);
                    return;
                }
                // 다음 지점이 범위 안에 있고, 방문하지 않았다면 queue에 넣는다.
                if (next > 0 && next < visited.length && visited[next] == 0) {
                    queue.add(next);
                    visited[next] = visited[temp] + 1;
                }
            }
        }
    }
}

Reference

• https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%801697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88