[백준] 22856번: 트리 순회 (C++)

문제 링크

22856번: 트리 순회

---

요즘들어 또 비가 주륵주륵 내리기 시작합니다... 여름이 다 가고 있기도 하구요.

이럴 때일수록 감기에 조심해야 됩니다! 이 글을 보는 모든 분들 환절기에 감기 안걸리고 건강하시길 기원하겠습니다! 🙋‍♂️

이전 글에 이어서 트리 관련 문제를 풀어보겠습니다~

풀이

DFS로 풀이하면 됩니다. (문제의 숨겨진(?) 트릭을 발견하면 쉽습니다)

문제에서 백트래킹에 의한 중위순회를 그림으로 보여주고 있습니다.

그러고나서 순회의 횟수를 세라고 하고 있습니다. 하지만 이 문제엔 숨겨진 방법이 존재합니다!

그림을 잘 관찰해보면, 맨 오른쪽 간선들(파란색 부분)만 한 번 이동한 것을 알 수 있습니다.

그렇습니다. 중위순회를 모두 거쳐서 횟수를 세어볼 수도 있겠지만,

이 문제에서 그것보다 더 효율적인 방법은 맨 오른쪽 간선의 수만 구해준 뒤 적절하게 계산만 해주면 되는 것입니다.

맨 오른쪽만 DFS로 탐색한 간선의 수를 1번으로 치고, 나머지 정점의 수는 2배를 해주면 됩니다.

식으로 나타내면 \(rcnt\)를 오른쪽 정점의 수라고 했을 때, \((n - rcnt) * 2 + (rcnt - 1)\) 가 되겠습니다.

 

(\((rcnt - 1)\)은 간선의 수를 구하기 위해 1을 뺀 것입니다.)

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

pair<int,int> tree[100001];
int rcnt;

void rtravel(int cur) {
  rcnt++;
  auto [lch, rch] = tree[cur];
  if (rch != -1) rtravel(rch);
}

void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    tree[a] = {b, c};
  }
  rtravel(1);
  cout << (n - rcnt) * 2 + rcnt - 1;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

 

배운점

• 중위순회를 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!