Even Idiots Can Make Game

백준 16953 S2 A → B

Date/Lastmod
Section
PS
Title
백준 16953 S2 A → B
Ps-Tags
트리너비 우선 탐색깊이 우선 탐색
Solved
04-21/25

#1 트리 탐색 문제로 접근

$A$를 루트로 하는 트리에서 존재 여부를 알 수 없는 $B$ 노드를 탐색하는 문제로 환원할 수 있다.

예를 들어 다음과 같은 트리를 그릴 수 있다.

각 노드가 $\times 2$를 취한 자식과, $\times 10 + 1$를 취한 자식을 갖는 이진 트리가 된다.

위 예에는 $B$ 노드가 트리 내 어딘가에 존재하지만, 사실 문제에 따르면 $B$가 아예 존재하지 않을 수도 있다.

$B$의 존재 여부에 따라

최단 경로에는 당연히 너비 우선 탐색을 사용하는 것이 좋다.

#2 너비 우선 탐색으로 $B$ 찾기

탐색 경로는 위와 같다. 최단 경로임이 보장된다. 코드는 아래와 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <queue>

using namespace std;

constexpr int NO_PATH = -1;

int A, B;

int bfs(int a, int depth) {
  queue<pair<long long, int>> to_visit;
  to_visit.push({a, depth});

  while (!to_visit.empty()) {
    auto [cv, cd] = to_visit.front();
    to_visit.pop();

    // B 발견, 그리고 이것이 최단 경로이므로 빠른 종료.
    if (cv == B) {
      return cd;
    }

    // 왼쪽 자식
    long long p1 = cv * 2;
    // 오른쪽 자식
    long long p2 = cv * 10 + 1;

    // 왼쪽 자식이 B보다 작으면, 
    // 왼쪽 자식을 루트로 하는 서브트리를 탐색해 봐야함
    if (p1 <= B) {
      to_visit.push({p1, cd + 1});
    }

    // 오른쪽 자식이 B보다 작으면, 
    // 오른쪽 자식을 루트로 하는 서브트리를 탐색해 봐야함
    if (p2 <= B) {
      to_visit.push({p2, cd + 1});
    }
  }

  return NO_PATH;
}

int main() {
  cin >> A >> B;

  cout << bfs(A, 1);
}

#2 근데 DFS로도 통과할 수 있다.

사실 나는 별 생각 없이 풀었기 때문에 처음에는 아, 백트래킹 문제구나 DFS 써야지, 하고 DFS를 사용하였다.

DFS 쓸 때 주의할 점?

BFS를 사용하면 그래프 내에 $B$가 몇 개 있더라도, $A$로부터 가장 가까운 깊이의 $B$를 가장 먼저 발견한다.

하지만 DFS는 그런 보장이 없으므로, 추가적인 처리를 해주어야 한다. 사실 매우 비효율적이지만, 이 문제에서 어쨌든 통과하기는 한다.

코드는 아래와 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <algorithm>

using namespace std;

constexpr int NO_PATH = -1;

int A, B;

int bt(long long k, int depth) {
  // B를 일단 발견하였다.
  if (k == B) {
    return depth;
  } 

  if (k < B) {
    // 왼쪽과 오른쪽 자식에서 B 찾기를 시도
    int l = bt(2 * k, depth + 1);
    int r = bt(10 * k + 1, depth + 1);
    // 1. 왼쪽과 오른쪽 모두에서 B를 발견
    if (l != NO_PATH && r != NO_PATH) {
      return min(l, r);
    // 2. 왼쪽에서만 발견
    } else if (l == NO_PATH && r != NO_PATH) {
      return r;
    // 3. 오른쪽에서만 발견
    } else if (l != NO_PATH && r == NO_PATH) {
      return l;
    }
  } 

  // 트리를 다 뒤져봐도 B가 없습니다.
  return NO_PATH;
}

int main() {
  cin >> A >> B;
  cout << bt(A, 1);
}
comments powered by Disqus