[BOJ 1697] 숨바꼭질 (Java, 그래프 탐색)

 

---

문제 링크

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

1697번: 숨바꼭질

---

풀이

- 현재 위치, 상태(숫자)를 정점으로 보고 +1 , -1, *2 를 간선이라 정의하여 문제 풀이

- BFS 문제 풀이

- N = 100,000 이고, K = 0 인 경우 -1 을 10만번 하면 K에 도착함 

=> 최대치 100,000 이므로 Integer 풀이 가능

---

제출 코드

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

public class Main {
    static int N, M;

    static int[] DISTANCE = new int[100001];

    static boolean[] VISIT = new boolean[100001];

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        br.close();
    }

    static void bfs() {
        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        VISIT[N] = true;
        DISTANCE[N] = 0;

        while(!que.isEmpty()) {
            int x = que.poll();

            int y = x + 1;
            if(0 <= y && y <= 100000 && !VISIT[y]) {
                DISTANCE[y] = DISTANCE[x] + 1;
                VISIT[y] = true;
                que.add(y);
            }

            y = x - 1;
            if(0 <= y && y <= 100000 && !VISIT[y]) {
                DISTANCE[y] = DISTANCE[x] + 1;
                VISIT[y] = true;
                que.add(y);
            }

            y = x * 2;
            if(0 <= y && y <= 100000 && !VISIT[y]) {
                DISTANCE[y] = DISTANCE[x] + 1;
                VISIT[y] = true;
                que.add(y);
            }
        }
    }

    static void pro() {
        bfs();
        System.out.println(DISTANCE[M]);
    }

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