[백준/1697] - 숨바꼭질(JAVA)

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

---

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

---

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

풀이

---

public class bojtest {
    static int N, K, next;
    static int[] field;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        field = new int[100001];
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        field[N] = 1;
        if (N == K){
            System.out.println("0");
        } else {
            BFS(N);
        }
    }
    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        while (!queue.isEmpty()){
            int point = queue.poll();
            for (int i=0; i<3; i++){
                if (i==0){
                    next = point + 1;
                }
                else if (i==1){
                    next = point - 1;
                } else {
                    next = point * 2;
                }
                if (next == K){
                    System.out.println(field[point]);
                    return;
                }
                if (next >= 0 && next < 100001 && field[next] == 0){
                    queue.offer(next);
                    field[next] = field[point] + 1;
                }
            }
        }
    }

}

해설

---

'최단거리 길찾기'라는 말을 통해 BFS를 이용한 풀이임을 얼추 알 수 있다.

다른 문제와는 달리 방문 배열이 없어도 되는데, 방문 배열과 배열에 기록을 동시에 할 것이기 때문에 필요없다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        field = new int[100001];
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        field[N] = 1;
        if (N == K){
            System.out.println("0");
        } else {
            BFS(N);
        }
    }

 

먼저, N과 K 둘다 100,000 이내의 숫자기때문에 배열을 만들고 첫번째 시작부터 1을 준다.

static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        while (!queue.isEmpty()){
            int point = queue.poll();
            for (int i=0; i<3; i++){
                if (i==0){
                    next = point + 1;
                }
                else if (i==1){
                    next = point - 1;
                } else {
                    next = point * 2;
                }
                if (next == K){
                    System.out.println(field[point]);
                    return;
                }
                if (next >= 0 && next < 100001 && field[next] == 0){
                    queue.offer(next);
                    field[next] = field[point] + 1;
                }
            }
        }
    }

이번 문제는 BFS 펑션이 굉장히 중요한 문제였다.

큐를 선언하고 offer하는것까진 동일한데, 위치를 잘 설정해 주어야 한다.

next를 잘 설정하고, next == k일경우 바로 return문으로 빠져나오는 문장이 있어야 하고,

여태까지 작성한 !visited[x]와 같은 역할을 하는 field[next]==0을 만족하게 되면 offer를 해준다. 그리고 field 배열에 다시 기록해준다.

<BFS 실행 순서>

먼저 5 17이라는 인풋을 가지고 예를 들어 보자,

• 처음 [5]를 큐에 넣고 돌린다. 그러면 [5]와 연결되어 있는 [4,6,10]이 큐에 들어간다.
  • 현재 큐 = [4,6,10]
  • field[4] = field[6] = field[10] = 1로 채워진다.
• 그 다음은 4가 뽑혀서 [3,5,8]이 큐에 들어가는데, 5는 이미 방문했으므로 큐에 들어가지 않는다.
  • 현재 큐 = [6,10,3,8]
  • field[3] = field[8] = field[4]+1 = 2로 채워진다.
• 그다음은 6이 뽑혀서 [5, 7, 12]가 큐에 들어가야 하는데, 5는 이미 방문했으므로 큐에 들어가지 않는다.
  • 현재 큐 = [10, 3, 8, 7, 12]
  • field[7] = field[12] = field[6]+1 = 2로 채워진다.
• 그다음은 10이 뽑혀서 [9,11,20]이 큐에 들어간다.
  • 현재 큐 = [3,8,7,12,9,11,20]
  • field[9] = field[11] = field[20] = field[10] +1 = 2로 채워진다.
• 그 다음은 3이 뽑혀서 [2,4,6]이 큐에 들어가야 하는데, 4와 6은 이미 방문했으므로 큐에 들어가지 않는다.
  • 현재 큐 = [8,7,12,9,11,20,2]
  • field[2] = field[3] + 1 = 3으로 채워진다.
• 그 다음은 8이 뽑혀서 [7,9,16]이 큐에 들어가야 하는데, field[7]과 field[9]는 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [7,12,9,11,20,2,16]
  • field[16] = field[8] + 1 = 3
• 그 다음은 7이 뽑혀서 [6,8,14]가 큐에 들어가야 하는데, field[6]과 field[8]은 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [12,9,11,20,2,16,14]
  • field[14] = field[7] + 1 = 3
• 그 다음은 12가 뽑혀서 [11,13,24]가 큐에 들어가야 하는데, field[11]은 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [9,11,20,2,16,14]
  • field[13] = field[24] = field[12] + 1 = 3
• 그 다음은 9가 뽑혀서 [8,10,18]이 큐에 들어가야 하는데, field[8]과 field[10]은 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [11,20,2,16,14,18]
  • field[18] = field[9] + 1 = 3
• 그 다음은 11이 뽑혀서 [10, 12, 22]가 큐에 들어가야 하는데, field[10]과 field[12]는 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [20,2,16,14,18,22]
  • field[22] = field[11] + 1 = 3
• 그 다음은 20이 뽑혀서 [19,21,40]이 큐에 들어간다.
  • 현재 큐 = [2,16,14,18,22,19,21,40]
  • field[19] = field[21] = field[40] = field[20] + 1 = 3
• 그 다음은 2가 뽑혀서 [1,3,4]가 큐에 들어가야 하는데, field[3]과 field[4]는 이미 숫자가 있으므로 큐에 들어가지 않는다.
  • 현재 큐 = [16,14,18,22,19,21,40.1]
  • field[1] = field[2] + 1 = 4
• 그 다음은 16이 뽑혀서 [15,17,32]가 큐에 들어가야 하는데, 17은 우리가 원하는 Target이므로 field정보를 출력한다
  • field[17] = field[16] + 1 = 4

생각해보면, 숫자들이 전부 접근하는 최솟값임을 알 수 있다. 이렇게 늘어놓아서 굉장히 길어 보이지만, 사실은 굉장히 빠르게 연산이 되고 있다. 

 

다시 백트래킹을 해보면, 17까지 이르는 동안

5 > 4 > 8 > 16 > 17로 해왔지만, 같은 5뎁스 안에

5 > 10 > 9 > 18 > 17도 경로가 될 수 있음을 알 수 있다.

 

다른 문제에서, 이 최단 경로가 몇개인지를 찾아보도록 하자.