[백준] 1697번 숨바꼭질 - Java[BFS]

[백준] 1697번 숨바꼭질 - Java[BFS]

 

문제 출처

 

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

1697번: 숨바꼭질

---

※ 풀이

수빈이가 동생을 찾는 가장 빠른 시간을 구해야 하는 문제이다.

최단 시간을 구하는 문제이므로 BFS 를 이용한다.

이 때 각 정점은 점 위치, 간선사이의 가중치는 1초로 모두 동일하므로 bfs 로 풀 수 있다.

 

bfs 로 갈 수 있는 점들을 한단계씩 진행해보면서 목적지에 도달하면 종료시키면 된다.

---

※ 주의할 점

탐색하는 정점의 위치가 10만을 넘었다가 가는것이 최단경로 일 수 있다.

따라서 안전하게 10만*2 =20만을 갈 수 있는 범위 내 경로로 잡고 풀었다.

 

---

※ 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        int MAX = 200000;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");

        boolean[] isVisited = new boolean[MAX];
        int[] count = new int[MAX];
        int n = Integer.parseInt(strings[0]);
        int k = Integer.parseInt(strings[1]);

        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        isVisited[n] = true;
        count[n] = 0;

        while (!queue.isEmpty()) {
            int now = queue.remove();

            //x+1
            if (now + 1 < MAX) {
                if (!isVisited[now + 1]) {
                    queue.add(now + 1);
                    isVisited[now + 1] = true;
                    count[now + 1] = count[now] + 1;
                }
            }

            //x-1
            if (now - 1 >= 0) {
                if (!isVisited[now - 1]) {
                    queue.add(now - 1);
                    isVisited[now - 1] = true;
                    count[now - 1] = count[now] + 1;
                }
            }

            // x*2
            if (now * 2 < MAX) {
                if (!isVisited[now * 2]) {
                    queue.add(2 * now);
                    isVisited[now * 2] = true;
                    count[2 * now] = count[now] + 1;
                }
            }
        }

        System.out.println(count[k]);
    }
}

---