(BOJ)かくれんぼ1679号

質問する

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

に近づく

最初はDFSを考えていましたが、解いてみるとどこで止まるべきかわかりました.果たしてこの道を通って最適な経路を見つけることができるかどうかは曖昧で、最終的にBFSに近づいて解くことができる.
問題自体は難しくないが,余分な(誤った)考えをコードに反映するために時間を浪費している.

誤った考え

秀斌と妹の位置を入力すると、無条件に秀斌の位置<=妹の位置(N<=K)を入力し、問題は簡単になります.

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

こうして二人の位置を変える文法が加わった.

反例

瞬間移動時にX(現在の位置)＊2に移動できます.
しかし、二人の位置を変えれば、X／2でもよいので、問題の条件に合わない.

誤った考え

アクセスするかどうかの配列の大きさは,スビンの位置と弟の位置の中でより大きな値+1である.

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

考えが少し短い.1の代わりに+2を使うことは可能です.

反例

N = 15, K = 29
15->30->29、答えは2です.
ただし、上記のようにコードを記述すると、アクセスの最大インデックスは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();
  }
}

リファレンス

問題の入力値範囲を十分に考慮し,アクセス配列の大きさを100001とし,前述したように,スビンと弟の位置の最値+2も正解である.逆に探索範囲が縮小したほうがいいかもしれません.

上が最高価格+2下が100001のときはあまり差がありません...メモリサイズにこだわるよりも、十分なメモリを与えるほうがいいです.