백준 16953 S2 A → B

문제: A → B

트리 탐색 문제로 접근

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

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

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

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

BB의 존재 여부에 따라

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

너비 우선 탐색으로 BB 찾기

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

#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);
}

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

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

DFS 쓸 때 주의할 점?

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

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

코드는 아래와 같다.

#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);
}

← 글 목록