(BOJ) 숨바꼭질_1679번

문제

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

접근

처음에는 DFS를 먼저 떠올렸지만 풀다보니 어디서 멈춰야 할지? 과연 이 길을 통해 최적의 경로를 찾을 수 있을지 애매하다고 느껴 결국 BFS로 접근하여 풀게 되었다.

문제 자체는 어렵지는 않지만 쓸데없는(틀린) 생각을 코드에 반영하느라 시간을 날렸던 것 같다.

틀린 생각 1

수빈이와 동생의 위치를 입력받고 무조건 수빈이의 위치 <= 동생의 위치 (N <= K)로 두면 문제가 간단해질 것

    if (n > k) {
      int tmp = n;
      n = k;
      k = tmp;
    }

이렇게 둘의 위치를 바꾸는 구문을 넣었는데...

반례

순간이동 시 X(수빈이의 현재 위치) * 2 로 이동 가능하다.
하지만 둘의 위치를 바꿔버리면 X / 2도 가능하다는 말이 되기 때문에 문제의 조건에 맞지 않다.

틀린 생각 2

방문 여부에 대한 배열의 크기를 수빈이의 위치와 동생의 위치 중 더 큰 값 + 1로 두면 된다.

    int size = Math.max(n, k) + 1;
    visited = new boolean[size];

생각이 좀 짧았다. +1 대신 +2를 하면 가능한 이야기다.

반례

N = 15, K = 29
15 -> 30 -> 29 로 답은 2가 된다.


하지만, 위처럼 코드를 작성해버리면 visited의 max index는 29가 되어버리고 (size = 29 + 1 = 30 이므로) 30 지점에 방문하지 못하게 된다.

코드

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

public class Main {

  static boolean[] visited = new boolean[100001];
  static int n;
  static int k;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");

    n = Integer.parseInt(inputs[0]);
    k = Integer.parseInt(inputs[1]);

    Queue<Integer> q = new LinkedList<>();
    q.add(n); // 위치
    q.add(0);
    while (!q.isEmpty()) {
      int num = q.remove();
      int count = q.remove();
      visited[num] = true;

      if (num == k) {
        bw.write(Integer.toString(count));
        break;
      }

      if (0 <= num * 2 && num * 2 < visited.length && !visited[num * 2]) {
        q.add(num * 2);
        q.add(count + 1);
      }

      if (0 <= num + 1 && num + 1 < visited.length && !visited[num + 1]) {
        q.add(num + 1);
        q.add(count + 1);
      }

      if (0 <= num - 1 && num - 1 < visited.length && !visited[num - 1]) {
        q.add(num - 1);
        q.add(count + 1);
      }
    }

    bw.flush();
    bw.close();
    br.close();
  }
}

참고

넉넉히 문제의 입력값 범위를 고려하여 visited 배열의 크기를 100001로 두긴 했는데 위에서 말했던 것 처럼 수빈이와 동생의 위치의 최댓값 + 2로 해도 정답이다. 오히려 탐색 범위가 줄어들어서 좋을지도 모르겠다.

위가 최댓값 + 2, 아래가 100001로 적용했을 때인데 별 차이는 없더라... 메모리 크기에 집착하다 실수하느니 넉넉히 주고 풀어도 무방할 것 같다.