Q. 1697 자바 : 숨바꼭질

Q. 1697 자바 : 숨바꼭질

 

문제 : boj.kr/1697

실버 1 난이도의 문제이다.

 

두 점 N, K가 주어지고, N이 이동할 수 있는 방식은 총 3개이며 각각 1초가 소요된다면(N + 1, N - 1, N * 2)N이 K로 갈 수 있는 가장 빠른 시간을 구하는 문제이다.

 

만약 그래프 탐색 관련 문제를 풀고 있지 않았다면처음 이 문제를 봤을 때 그래프 탐색 문제라고 생각하지 못했을 것 같다.고민해보니 세가지 이동방식에 대한 BFS를 이용하면 풀 수 있을 것 같아 이 방식을 이용해서 풀었다.

 

1. 정점 N에서 이동 가능한 세 가지 방식에 따른 좌표를 큐에 넣는다.2. 만약 방문했다면 재방문하지 않는다.(가장 먼저 방문한 경우가 가장 빠른 경우이므로 재방문했다면 더 빨라질 수는 없다.)

 

시간복잡도를 계산하기 위해 범위를 찾아보니0 <= N ,K <= 100,000이므로 최악의 경우는 N이 100000, K가 0인 경우에-1을 이동하는 방식으로 100,000번 이동해야 K의 위치에 갈 수 있다.따라서 시간초과는 걱정하지 않아도 된다.

 

풀이는 아래와 같다.

import java.io.*;
import java.util.*;


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, K;

    static int MAX_VALUE = 100000;

    static int[] dist;
    static boolean[] visit;
    static void input() {

        N = scan.nextInt();
        K = scan.nextInt();
        dist = new int[MAX_VALUE + 1];
        visit = new boolean[MAX_VALUE + 1];
    }

    static void bfs(int s) {

        Queue<Integer> que = new LinkedList<>();
        que.add(s);
        dist[s] = 0;
        visit[s] = true;

        while (!que.isEmpty()) {

            int cur = que.poll();
            int nx = cur + 1;
            int ny = cur - 1;
            int nz = cur * 2;
            if (nx <= MAX_VALUE && !visit[nx]) {
                que.add(nx);
                visit[nx] = true;
                dist[nx] = dist[cur] + 1;
            }
            if (ny >= 0 && !visit[ny]) {
                que.add(ny);
                visit[ny] = true;
                dist[ny] = dist[cur] + 1;
            }
            if (nz <= MAX_VALUE && !visit[nz]) {
                que.add(nz);
                visit[nz] = true;
                dist[nz] = dist[cur] + 1;
            }
        }
    }

    static void pro() {

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

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도,
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}