오일러 경로 테크닉 (Euler Tour Technique)
ETT라고도 불리는 이 테크닉은 DFS를 이용한 트리 관련 테크닉입니다. 구체적으로는, 어떤 트리가 있을 때, 해당 트리에 속한 노드 N과, 노드 N을 루트로 가지는 서브트리에 속한 모든 노드들을 하나의 연속된 구간으로 표현할 필요가 있을 때 사용됩니다.
음, 이를 좀 다르게 말해보면, 일반적인 트리를 세그먼트 트리로 변환시킬 때 필요한 테크닉입니다. 방법에 대해서는 이 글에서 설명할 예정이지만, 결론부터 말하자면, 트리의 각 노드들에 구간 [DFS 함수가 시작된 시점, DFS 함수가 종료된 시점]을 부여해주면 됩니다.
이런 모양의 트리가 있습니다. 이제 이 트리에 대해서 오일러 경로 테크닉을 사용해볼텐데, 그전에 먼저 트리의 순회 방법부터 정해야 합니다. 저는 전위 순회로 트리를 돌면서 노드들이 가지게 되는 구간을 구해보겠습니다. 구간은 앞서 말했듯이 [DFS 함수가 시작된 시점, DFS 함수가 종료된 시점]을 기록하겠습니다.
전위 순회로 돌면서 구간을 기록했습니다. 어떤 느낌인지 감이 오실 겁니다. 검정색으로 쓴 숫자가 진입한 시점, 청록색으로 쓴 숫자가 종료된 시점입니다. 여기서 배열 두 개를 정의하고 가겠습니다.
in[N] = N번 노드의 DFS 함수가 시작된 시점
out[N] = N번 노드의 DFS 함수가 종료된 시점
오일러 경로 테크닉은 이런 방식으로 각 노드들이 가지고 있는 구간을 관리합니다. in[5] = 7, out[5] = 9와 같이 말이죠
이를 코드로 구현하면 이렇게 될 겁니다.
int cnt = 0;
// Euler Tour Technique
void go(int node) {
visited[node] = true;
in[node] = ++cnt;
for (int next : v[node]) {
if (visited[next]) continue;
go(next);
}
out[node] = cnt;
}
이제 위의 트리의 노드들을 일자 형태로 쭉 펴줄겁니다. 이게 무슨 소리인가 싶지만, 그냥 각 노드들의 in[k]의 값을 기준으로 노드를 오름차순 정렬해주면 됩니다. 굉장히 간단하죠. 위의 트리가 일자로 펴진 모양은 아래와 같은 모양일 겁니다.
이제 이 펴진 노드들을 이용하면, 트리에 속한 어떤 노드 N에 대해서, N을 루트로 하는 서브트리의 모든 노드들을 연속된 구간으로 표현할 수 있습니다. 이게 무슨 말인가 하면 아래 그림을 다시 봐보죠. 아래 그림들은 N번 노드와 그 서브트리에 속한 모든 노드들이 어떤 구간에 속해있는지 보여줍니다.
이처럼 트리에 속한 어떤 노드 N과 그 서브트리에 속한 노드들을 연속적인 구간으로 표현할 수 있게 되었습니다.
이때 중요한 점은 바로 "연속적인" 구간이라는 점입니다. 연속적인 구간을 관리하는 자료구조... 그렇습니다. 바로 세그먼트 트리죠.
처음에 설명했던 것처럼, ETT로 일반적인 트리를 세그먼트 트리로 변환시킬 수 있습니다. 그 모양은 바로 아래와 같겠죠.
아까 일자 형태로 편 노드들은 세그먼트 트리의 리프 노드들이 될 겁니다. 괄호 안에 적힌 숫자는 각 노드들의 in 값 구간입니다. 노드 번호가 아님에 유의합시다.
14268번: 회사 문화 2
영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하
www.acmicpc.net
이 문제를 한번 봐보죠.
상사가 직속 부하를 칭찬하면, 그 부하의 직속 부하를 연쇄적으로 칭찬한다고 합니다. 그리고 직속 상사와 직속 부하의 관계를 그래프로 나타내보면 트리의 모양이 되죠. 따라서 2개의 쿼리는 이렇게 해석할 수 있습니다.
1번 쿼리: i번째 노드를 루트로 하면서 i번째 노드를 포함하는 서브트리의 모든 노드들에 w를 더한다.
2번 쿼리: i번째 노드의 값을 출력한다.
일단 먼저 Naive하게 접근해봅시다. 2번 쿼리는 어찌저찌해서 O(1)에 가져온다 해도, 1번 쿼리는 O(N)이 걸립니다. 쿼리의 개수까지 생각해보면 O(NM)이 될 거고, 이는 당연히 TLE를 받습니다. 따라서 이 문제를 풀기 위해서는 O(N)을 로그 시간 이하로 최적화시켜야 합니다.
먼저 이 문제에서 구간이 보이는 것 같습니다. 어떻게든 루트 노드와 그 서브트리에 속한 노드들을 구간으로 나타낼 수 있으면 될 것 같은데...! 이때 사용하는 것이 바로 오일러 경로 테크닉입니다.
ETT를 사용해서 입력받은 트리를 세그먼트 트리로 변환하고, in[i]와 out[i]를 구간으로 가지는 구간 업데이트를 진행해주면 1번 쿼리를 잘 수행할 수 있겠죠. 물론 이 문제는 효율적인 구간 업데이트를 요구하기 때문에 Lazy propagation을 이용해 최적화시켜줍시다.
2820번: 자동차 공장
상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다.
www.acmicpc.net
이 문제도 위 문제와 같은 맥락의 문제입니다. 다만, 이 문제에서는 초기 값이 주어지기 때문에 그 값을 바탕으로 세그먼트 트리를 만들어줘야 합니다. 주의해야할 점은, 초기 인덱스 값을 세그먼트 트리의 리프 노드에 바로 매칭 시키면 안된다는 점입니다. 오일러 경로 테크닉을 사용한 결과로 재정렬된 인덱스 값을 세그먼트 트리의 리프 노드에 매칭시켜주어야 합니다. 즉, ETT 쓰고 난 뒤에 초기 세그먼트 트리를 만들어줘야 합니다.
댓글