[백준] 1697번 : 숨바꼭질 – JAVA [자바]

 

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

1697번: 숨바꼭질

 

---

 

• 문제

 

---

• 문제 풀이

백준 1697번 숨바꼭질은 그래프, 그중에서도 BFS를 써서 푸는 난이도 실버 1의 문제이다. 왜 BFS를 쓰냐면 BFS는 Queue를 이용해서 count를 구하기 쉽지만 DFS는 재귀 함수로 구현되기 때문에 카운트를 구하기가 쉽지가 않다. 이 문제에서는 수빈이의 위치 n, 그리고 동생의 위치 k가 주어진다. 그리고 수빈이의 위치가 X이면 1초 후에 X-1, X+1, 2X로 이동할 수 있다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 인지만 구하면 된다. 

 

문제에서 주어진 예시를 한번 보겠다. 수빈이의 위치는 5이고 동생의 위치는 17이다. 따라서 0초에 있는 곳은 표시를 해두겠다.

1초 때는 X-1, X+1, 그리고 2X로 이동할 수 있어서 4, 6, 그리고 10으로 이동할 수 있다. 표로 표현하면 다음과 같다.

1초에 4, 6, 그리고 10으로 이동한 것을 볼 수 있다.

 

이미 간 곳을 제외하고 그다음에는 :

위치 4에서 3, 8로 갈 수 있다.

위치 6에서 7, 12로 갈 수 있다.

위치 10에서 9, 11, 20으로 갈 수 있다.

 

그다음에는

3에서 2로 갈 수 있다.

7에서 14로 갈 수 있다.

8에서 16으로 갈 수 있다.

9에서 18로 갈 수 있다.

11에서 22로 갈 수 있는데 20 이상은 편의를 위해서 제외시키겠다.

12에서는 13, 24로 갈 수 있다.

20에서 19, 21, 40으로 갈 수 있다.

 

그다음에는

2에서 1로 갈 수 있다.

13에서 26으로 갈 수 있다.

14에서 15, 30으로 갈 수 있다.

16에서 17, 32로 갈 수 있다. 

 

16에서 17로 가기 때문에 4초가 걸린다.

 

---

• 코드

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        if (n == k) {
            System.out.println(0);
            return;
        }
        boolean[] visited = new boolean[100001];
        visited[n] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        int size = q.size();
        int count = 0;
        while (true) {
            count++;
            size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.remove();
                visited[x] = true;
                if (x-1 == k || x+1 == k || x*2 == k) {
                    System.out.println(count);
                    return;
                }
                if (x-1 >= 0 && !visited[x-1]) {
                    visited[x-1] = true;
                    q.add(x-1);
                }
                if (x+1 <= 100000 && !visited[x+1]) {
                    visited[x+1] = true;
                    q.add(x+1);
                }
                if (x*2 <= 100000 && !visited[x*2]) {
                    visited[x*2] = true;
                    q.add(x*2);
                }
            }
        }
    }
}

 

---

• 후기

예전에 그래프 문제를 처음 풀 때는 언제 DFS를 써야 되는지, BFS를 써야 되는지 헷갈렸었다. 만약에 헷갈린다면 이렇게 생각해보면 좋을 듯하다. count를 세야 되면 DFS, 그리고 필요 없으면 DFS나 BFS 중 편한 것을 쓰면 된다.