[백준] 1697번: 숨바꼭질

💡문제 분석 요약

수빈의 위치를 N, 동생의 위치를 K로 입력받는다. 수빈의 위치를 X라고 할 때 X-1, X+1, 2*X로 이동할 수 있고, 이동할 경우 1초가 소요된다. 이 때 수빈이 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• 수빈의 위치 `n` 과 동생의 위치 `k` 를 입력받는다.
• 위치에 따른 이동 시간을 저장하는 `time`배열을 생성한다. (0 초기화)
  • `time`배열의 값이 0일 경우 방문하지 않은 것으로 처리한다. (= 이동 시간이 0)
• `time[n]` 을 1로 설정하고, BFS를 이용해 `k`위치까지의 이동 시간을 계산한다.
• BFS 메서드
  • 시작 위치를 큐에 넣는다.
  • 큐가 빌 때까지:
    • 큐의 맨 앞의 값을 가져온다. ⇒ 현재 위치 `X`
    • 현재 위치 `X`의 `X-1, X+1, 2*X`의 위치에 대해 (⇒ `cx`):
      • `cx`가 범위 0 ~ 100,000에 속하고, 아직 방문하지 않은 경우
        • `cx`를 큐에 넣는다.
        • `time[cx]` 에 “현재까지의 이동 시간 +1”을 저장한다.
          (`X` 에서 `cx` 로 이동하는데 1초가 걸리기 때문)
      • 만약 해당 위치가 `k`일 경우 BFS 종료
• 최소 이동 시간은 `time[k]-1` 이다. (이동 시간을 1부터 시작했기 때문에 1을 뺌)

 

💡코드

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

public class Main {
    static int[] time = new int[100001];

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        while(!q.isEmpty()) {
            int x = q.poll();
            int[] cx = {x-1, x+1, x*2};

            for(int i=0; i<3; i++) {
                if(cx[i] >= 0 && cx[i] <= 100000 && time[cx[i]] == 0) {
                    q.offer(cx[i]);
                    time[cx[i]] = time[x] + 1;
                }
                if(cx[i] == k) return;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] str = new BufferedReader(new InputStreamReader(System.in)).readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);

        time[n] = 1;
        bfs(n);

        int time = time[k]-1;
        System.out.println(time);
    }
}

 

💡시간복잡도

$V$ 를 노드의 수, $E$ 를 간선의 수라고 할 때, 시간복잡도는 $O(V+E)$이다.

결과적으로 $O(N)$이다.

 

💡 느낀점 or 기억할정보

문제를 보고 BFS로 풀어야겠다는 생각을 했지만, 알고리즘 설계하는데 오래걸렸다. 더 복잡한 문제가 나오면 어려워질 것 같다.ㅠ

스터디하는 팀원은 ` Queue<int[]> qu =new ArrayDeque<>(); `를 이용해서 큐에 위치와 이동 정보를 함께 저장했다. 가독성은 이 방법이 더 좋을 것 같다. 그리고 ArrayDeque를 사용했는데, 찾아보니 LinkedList보다 ArrayDeque를 이용하는 것이 메모리 효율성이나 성능 면에서 더 뛰어나서, 특별한 이유가 없다면 Queue 구현체로 ArrayDeque를 사용하는 것을 권장한다고 한다. 다음에 큐를 이용해서 문제를 풀 때는 ArrayDeque를 이용해 봐야겠다.