[C++] 백준 2233번 사과나무

문제

사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무의 예이다. 나무같이 보이기 위해서 그림은 루트를 아래에 그린다.

이러한 사과나무에 서식하는 벌레를 생각해 보자. 이 벌레는 이 사과나무의 루트에서 DFS 순서로 탐색을 하게 된다. 자식이 여러 개인 경우에는 (뒤집혀진 그림에서) 왼쪽을 먼저 방문하게 된다. 이러한 탐색을 하면서, 새로운 노드를 방문할 때 0을, 모든 자식 노드를 방문하고 리턴할 때 1을 나열하면 하나의 이진 수열이 된다. 위의 그림으로 이진 수열을 만들면 다음과 같다.

이진수의 각 숫자들은 그 숫자가 0이든 1이든 하나의 정점에 대응되게 된다. 즉 0의 경우에는 새로 방문되는 정점에 대응되고, 1의 경우에는 리턴하기 전에 있었던 정점에 대응된다. 위의 표에서는 각 숫자에 대응되는 정점도 표시하였다.

이러한 사과나무에서 썩은 사과가 발견된 경우에는 가지를 잘라 내어야 한다. 만약 우리가 어떤 정점을 제거하면, 그 정점과 그 자손 정점들이 모두 제거되게 된다. 위의 예에서 b를 제거하면 b, c, d가 모두 제거되게 된다.

만약 한 개의 사과가 썩은 경우라면 그 사과를 제거하면 되지만, 두 개의 사과가 썩은 경우라면 문제가 복잡해진다. 사과나무의 성질을 유지하기 위해서, 우리는 오직 한 개의 사과만 제거할 수 있다. 이 경우 루트를 제거하면 되지만, 루트를 제거하게 되면 멀쩡한 사과들을 많이 잃게 된다(제거되는 것은 잃는 것). 따라서 우리는 한 개의 사과를 제거하되, 이를 통해 두 개(이하)의 썩은 사과를 함께 제거하고, 그러면서도 가장 적은 개수의 멀쩡한 사과를 잃도록 잘라야 한다. 위의 예에서 c, d의 사과가 썩은 경우에는 b를 제거하면 된다.

사과나무에 대한 정보가 주어졌을 때, 제거해야 하는 사과를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N(1≤N≤2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리의 이진수에서 X번째의 숫자에 대응되는 정점과, Y번째 숫자에 대응되는 정점에 있는 사과가 썩었다는 의미이다. 이때 두 정점이 서로 같을 수도 있다.

출력

첫째 줄에 제거해야 할 사과를 나타내는 두 정수 i, j를 출력한다. 제거해야 할 사과를 Z라고 했을 때, 이는 Z를 방문할 때의 0의 위치와 Z에서 리턴될 때의 1의 위치가 이진수에서 각각 i, j 번째임을 나타낸다.

풀이

문제해결을 위한 아이디어는 간단하다. 주어진 두 노드의 최소 공통 조상을 찾으면 된다.
처음에는 무작정 이진수를 트리로 옮기고 다시 공통 조상을 찾아 해결은 했지만 코드가 매우 지저분했었는데 이후 다른 좋은 풀이가 있어서 참고해보았다.
트리를 만드는 대신 parent배열에 각 노드의 부모를 기록한다.
arr배열에는 각 노드가 나타난 위치를 기록한다.
이후 주어진 두 위치에 해당하는 노드를 찾은 후 첫번째 노드의 조상들을 전부 체크한다. 두번째 노드도 조상을 따라 올라가다 체크된 노드를 찾으면 해당 노드가 최소 공통 조상이 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

string str;
int n;
int a,b;
int parent[2001];
int arr[4010];
int check[2001];

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  cin >> str;

  cin >> a >> b;

  int p = 0;
  int child = 1;

  for (int i=1; i<=n*2; i++){
    if (str[i-1] == '0'){
      parent[child] = p;
      arr[i] = child;
      p = child;
      child++;
    }
    else{
      arr[i] = p;
      p = parent[p];
    }
  }

  int x = arr[a];
  int y = arr[b];

  while (x != 0){
    check[x] = 1; 
    x = parent[x];
  }
  
  while (!check[y]){
    y = parent[y];
  }

  for (int i=1; i<=n*2; i++){
    if (arr[i] == y)
      cout << i << " ";
  }
}