[Java] 백준 - 12851번: 숨바꼭질 2

5월 24일(금) - 그래프와 순회(12851번)

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

---

최초 생각 정리

---

문제점

---

풀이

(풀이출처 -> https://bcp0109.tistory.com/154)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {

    static int N,K;
    static int[] time = new int[100001];
    static int min_time = 987654321;
    static int count = 0;


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

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

        if(N >= K)
        {
            System.out.println((N-K) + "\n");;
            return;
        }

        bfs();
        System.out.println(min_time + "\n" + count);
    }

    static void bfs(){
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(N);
        time[N] = 1;

        while (!q.isEmpty())
        {
            int now = q.poll();
            if(min_time < time[now])
            {
                return;
            }

            for(int i=0; i<3; i++)
            {
                int next;

                if(i == 0)
                {
                    next = now + 1;
                }
                else if(i == 1)
                {
                    next = now - 1;
                }
                else
                {
                    next = now * 2;
                }

                if(next < 0 || next > 100000)
                {
                    continue;
                }

                if(next == K)
                {
                    min_time = time[now];
                    count++;
                }

                if(time[next] == 0 || time[next] == time[now] + 1)
                {
                    q.add(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}

---