오일러 투어(Euler Tour) 기초

오일러 투어?

오일러 투어는 트리에서 백트래킹을 할 때 그 흔적을 남기는 순회로 볼 수 있다.

 

트리에서 오일러 투어의 순서를 숫자로 기록한 그림

 

오일러 트리를 이용하면 DFS를 하면서 몇 번째 이동에 어떤 정점에 머무르는지, 어떤 부모 노드의 자식 중 가장 큰 번호가 무엇인지, 그리고 해당 정점이 어느 시점에 처음으로 방문되고 어느 시점에 마지막으로 방문되는지 파악할 수 있다.

 

오일러 투어로 무엇을 하려는지에 따라 그 구현이 달라지므로 위 경우들에 대한 구현을 소개한다.

1. x번째 이동에 도착한 정점

다음 코드는 DFS를 할 때 특정 시점에 방문한 노드를 기록한다.

vector<int> footprint;
vector<int> tree[100001];
bool discovered[100001];

void euler_tour(int node)
{
  footprint.push_back(node);

  for (int i: tree[node])
  {
    if (discovered[i])
      continue;
    
    discovered[i] = true;
    euler_tour(i);
    footprint.push_back(node);
  }
}

 

우선 foot_print 벡터에 node를 삽입하여 현재 node번에 도착했음을 알린다.

 

그다음 트리의 자식을 대상으로 DFS를 하는데 만약 자식이 방문 가능하다면 그 자식의 탐색이 끝날 때 다시 한번 node를 삽입한다.

 

이는 자식을 대상으로 한 순회를 마치고 자기에게 돌아왔다는 뜻을 가진다.

 

순회가 모두 끝나면 몇 번째 이동에 도착한 노드가 무엇인지 foot_print 벡터에서 바로 확인할 수 있다.

2. 특정 노드의 처음 방문 시점과 마지막 방문 시점

1번과 비슷하지만 특정 노드에 방문한 첫 번째 시점과 마지막 시점을 바로 알고 싶은 경우 다음과 같이 구현하면 된다.

int num = 1;
vector<int> tree[100001];
pii tour_inout[100001];
bool discovered[100001];

void euler_tour(int node)
{
  tour_inout[node].first = num++;

  for (int i: tree[node])
  {
    if (discovered[i])
      continue;
    
    discovered[i] = true;
    euler_tour(i);
  }

  tour_inout[node].second = num;
}

 

이러면 특정 노드의 자식에 대해 몇번 이동했는지 계산하기 편하다.

3. 특정 노드의 자손 중 가장 큰 번호 알아내기

DFS를 하면서 노드 번호를 새로 바꿔간다고 해보자. 그리고 특정 노드의 자손 수가 어느 정도인지, 그리고 마지막으로 방문한 자손이 몇 번인지 알고 싶으면 2번의 구현을 바꿔서 다음처럼 바꿀 수 있다.

int num;
vector<int> tree[100001];
pii tour_leaf[100001];
int node_conv[100001];
bool discovered[100001];

void euler_tour(int node)
{
  node_conv[node] = tour_leaf[node].first = ++num;

  for (int i: tree[node])
  {
    if (discovered[i])
      continue;
    
    discovered[i] = true;
    euler_tour(i);
  }

  tour_leaf[node].second = num;
}

 

num이 2번 구현과 어떤 차이점이 있는지 주목하라. 2번에서는 num을 1로 초기화해서 후위식으로 1을 더한 후 탐색을 이어갔지만 이 구현에서는 num을 0으로 초기화한 후 전위식으로 num에 1을 더해가며 탐색을 하고 있다.

 

이렇게 되면 tour_leaf의 first에는 현재 노드의 새로운 번호, second에는 자기에게 방문한 마지막 시점이 아니라 자신의 자손 중 마지막으로 방문한 노드의 번호가 기록된다.

 

또한 node_conv 배열에 새롭게 바뀐 노드 번호가 기록된다.

 

이 방법을 사용하여 자손의 수와 마지막으로 방문한 자손의 번호를 알 수 있게 된다.

연습하기

오일러 투어를 사용하는 문제를 풀어보자.

 

https://atcoder.jp/contests/abc213/tasks/abc213_d

D - Takahashi Tour

 

오일러 투어를 알고있는 상태에서 읽어보면 매우 쉬우니 설명은 생략한다.

 

지금까지 오일러 투어에 대해 알아보고 구현법 3가지를 알아보았다.

 

다음엔 오일러 투어와 다른 알고리즘을 결합해서 풀 수 있는 문제를 알아보도록 하자.

 

다음 편