[백준 JAVA] 13549 : 숨바꼭질 3

[백준 13549] 숨바꼭질 3 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

문제 조건 정리

 

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

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

---

입력

 

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

---

문제를 풀기 전

 

1. dp로 해결하는 문제인지, bfs로 해결하는 문제인지 헷갈렸음! 결국 bfs가 맞다고 생각함!
2. 순간이동이 0초가 걸리는게 매우 신경쓰였음!
3. 수빈이를 클래스로 정의하고 객체로 관리해야지 문제가 쉽게 풀릴 것 같다고 생각함!
4. 수빈이가 동생과 위치가 같거나, 수빈이가 동생보다 더 앞에 있는 조건(N>K)에 대한 예외를 처리하는게 깔끔하다고 생각함!

참고로 일반적인 bfs로 문제를 해결하려는 시도는 완벽히 실패함!

---

코드

 

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

public class Main {

    // 수빈 위치와 현재 걸린 시간을 클래스로 정의
    private static class Subin {
        int pos, time;

        public Subin(int pos, int time) {
            this.pos = pos;
            this.time = time;
        }

    }

    // 수빈이 (start)
    static int s;
    
    // 동생 (end)
    static int e;
    
    // 재방문 확인 배열
    static boolean[] visited;
    
    // 수빈이의 다음 위치를 저장할 배열
    // 성능 최적화를 위해서 스태틱으로 선언
    // 사실상 메인함수의 while문 밖에 적어도 무방하다고 생각
    static int[] nextPos = new int[3];

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

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        s = Integer.parseInt(stringTokenizer.nextToken());
        e = Integer.parseInt(stringTokenizer.nextToken());

        // 수빈이가 동생보다 앞에 있는 경우
        if (s > e) {
            System.out.println(s - e);
            return;
        } 
        
        // 수빈이와 동생이 동일한 위치에 있는 경우
        else if (s == e) {
            System.out.println(0);
            return;
        }

        // !! Queue가 아닌 Deque로 선언해야 함 !!
        // 수빈 객체를 앞뒤로 offer(add) 해야 하기 때문이다 (0-1 bfs)
        // 혹은 priorityQueue (다익스트라)
        Deque<Subin> deque = new ArrayDeque<>();
        
        // 배열의 크기로 e + 2가 최적의 수인지 확신할 수 없지만
        // 100_001과 같은 상수로 표현하고 싶지 않았음
        // 2를 더하는 것도 신경 쓰이긴 함
        // 참고: e+2와 100_001을 백준을 통해서 비교해보니 전자가 10% 내외로 효율적임
        visited = new boolean[e + 2];
        
        deque.offer(new Subin(s, 0));
        visited[s] = true;

        while (!deque.isEmpty()) {
            Subin current = deque.poll();

            // 종료 조건
            if (current.pos == e) {
                System.out.println(current.time);
                return;
            }

            nextPos[0] = current.pos * 2;
            nextPos[1] = current.pos - 1;
            nextPos[2] = current.pos + 1;

            for (int i = 0; i < 3; i++) {
            
                // 다음 위치로 움직일 수 있다면
                if (canMove(nextPos[i])) {
                    visited[nextPos[i]] = true;
                    
                    // 순간이동의 경우는 시간이 추가되지 않고
                    // 덱(deque)의 앞으로 삽입함 
                    if (i == 0) {
                        deque.offerFirst(new Subin(nextPos[i], current.time));
                    } 
                    
                    // 걸어서 이동하는 경우는 시간이 추가되며
                    // 덱의 끝으로 삽입함
                    else {
                        deque.offerLast(new Subin(nextPos[i], current.time + 1));
                    }
                }
            }

        }
    }

    // 수빈이가 이동할 위치가 올바른지 확인하며, 재방문도 확인함
    private static boolean canMove(int pos) {
        return 0 <= pos && pos < e + 2 && !visited[pos];
    }
}

 

---

문제를 풀고 난 후

 

여러가지 문제가 있었다!

문제가 어려웠다기보다 헷갈리는 포인트가 몇가지 있었는데 .. 한마디로 요약하자면 실력이 상당히 부족했다!

 

1. canMove 메서드

    첫 시도에는 pos를 0이상, e이하로 선언했었다!

반례 -> [입력] 2 7 [출력] 1
2 -> 4 -> 8 -> 7, 순간이동 2회, 걷기 1회로 1초 걸려야하는 반례를 통해서 내 코드의 문제를 찾았다.
나는 7이하까지만 canMove하다고 판단했기에 2 -> 3 -> 6 -> 7, 순간이동 1회, 걷기 2회로 2초가 걸리는 문제가 있었다.
그래서 다른 비슷한 반례들도 생각해보다가 머리가 복잡해져서 e+2미만 (e+1이하)로 제한하니 문제 자체는 해결되었다.
아직도 완벽한 정답이라고 확신할 수 없다.

        

2. 0-1 bfs

    사실 이게 더 중요함!

가중치가 주어지는 그래프를 bfs로 풀기 위해서는 우선순위큐를 사용해야 한다는 사실을 잊었다!
순간이동에 0초가 걸린다는게 찝찝했던 이유였을까!
다익스트라로 문제를 풀려고 했으나 0-1 bfs가 떠올랐다!
이전에도 백준 문제에서 비슷한 실수를 한 적이 있기 때문이다!

0-1 bfs 란?
이동에 걸리는 시간(가중치)가 0, 1로 나뉜 경우
가중치가 0인 간선을 통과한 노드(순간이동 수빈이)는 덱의 맨 앞에 넣어서 큐에서 먼저 나올 수 있게 삽입한다. (offerFirst)
가중치가 1인 간선을통과한 노드(걷기 수빈이)는 일반적인 offer(offerLast)를 통해서 삽입한다.

정확하게 증명해보지는 않았지만 외우듯이 했다.
가중치가 없는 간선을 통과한 노드를 덱의 앞에 넣으면 최적화될 것 같아서 찾아보지 않았다. 

정확한 정의를 알고 싶은 분들은 검색해보시고 저도 이해시켜주세요!

    

상당히 고생했다!

2 7 반례를 생각해내는게 제일 오래걸렸다!