THE100YEARSWAR 백년전쟁 풀이

문제: https://algospot.com/judge/problem/read/THE100YEARSWAR

문제 해석

1,2번 왕을 제외한 모든 귀족은 종신 관계를 가지고 있으며

입력에서 종신관계의 순서는 임의의 순서로 들어오나 결국에는 1,2번을 루트로 한 두개의 트리가 완성된다.

들어오는 순서가 임의이기 때문에 입력을 받으면서 전처리는 불가능하다. 모든 입력을 다 받고 난 뒤에 전처리를 행해야 한다.

한 귀족이 배신을 하면 그 귀족 아래의 모든 귀족이 배신을 한다. 즉 그 배신하는 귀족을 루트로하는 부분트리내 모든 노드가 배신을 한다.

입력 받기

예를 들면 귀족이 총 19명이고 1~19번 귀족=노드의 입력이 이런 형태로 들어왔다고 합시다.

이러한 트리 구조를 받을 수 있는 자료형을 먼저 만들어야 합니다.

이 경우는 노드의 개수가 초기에 정해져 있고 늘어나거나 줄어들일이 없으니 단순 배열로 구현하면 됩니다.

또한 자식의 개수가 정해져있지 않으니 동적 자료구조를 사용해야 하는데 순회를 하기 위해 연속 주소공간을 갖는 자료형이 좋습니다.

C++ 기준으로 설명 하겠습니다.

vector<int> child[20];

1번부터 19번까지 노드 자식 정보를 정보를 받기 위해 20개짜리 백터 배열을 선언했습니다. (백터는 연속 주소공간을 갖는 동적 배열)

child[1]은 1번 노드의 자식들 번호를 저장하는 배열을 뜻합니다.

입력은 이런 식으로 받게 됩니다.

child[19].push_back(3);

그럼 위 그림 형태의 트리가 완성됩니다.

접근법1

일단 단순 무식한 방법으로 접근하겠습니다.

이 문제에서는 쿼리가 2가지가 들어옵니다. 배신과 같은 팀인지 확인하는 것. (배신=토글. 토글은 on/off를 의미합니다.)

여기서 두 가지 선택지가 존재합니다.

1. 배신 쿼리가 들어올때 해당 노드 하나만 배신한다. 같은 팀인지 체크할때 모든 부모 노드를 방문하며 루트 노드까지 배신 여부를 체크하며 올라간다.

2. 배신 쿼리가 들어올때 해당 노드와 해당 노드의 모든 자식 노드들이 배신한다. 같은 팀인지 체크는 바로 확인한다.

일단 1번 방법의 경우 같은 팀인지 체크 하려면 자식노드가 부모노드의 번호를 알고 있어야 합니다.

또한 모든 부모 노드가 1개의 자식만을 갖고 있는 경우라면 문제처럼 50000개의 노드가 주어질때 시간안에 수행하기 힘듭니다. 배신 쿼리는 무지 빠르지만 팀 확인 쿼리는 무지 느립니다.

이것은 2번 방법도 마찬가지입니다. 배신 쿼리는 무지 느리지만 팀 확인 쿼리는 무지 빠릅니다.

하지만 2번 방법의 경우 최적화 할 여지가 있습니다. 노드들을 방문할때 느린 이유는 이 노드들이 연속되어있지 않아 여기저기 왔다갔다 방문을 하기 때문입니다.

때문에 자손 노드들을 연속된 주소 공간에 놓아 빠르게 방문을 하도록 최적화 할 수 있습니다. 트리를 일차원적 공간으로 변형합니다.

자손 노드를 연속되게 방문 하는법. 바로 전위 순회입니다. 전위 순회하면 모든 자손노드는 모든 조상노드의 우측에 있게 됩니다.

이 입력을 1,2번 노드로부터 전위 순회하게 되면

1 19 12 3 16 6 4 9 15 8

2 14 10 18 11 7 17 5 13

이런 순서로 방문하게 되어 연속된 주소 공간에 놓을 수 있습니다.

그리고 자기 자신의 자손 노드가 어느 위치에서 끝나는지 기억해두면 연속되게 자손들을 방문 할 수 있습니다.

여기서 필요한 자료형이 세가지 있습니다.

바로 팀을 나타내기 위한 자료형과 노드의 번호와 전위 순회 순번 관계를 대응시키는 변수와 마지막 자손의 위치를 기억하는 변수 입니다.

int team[20]={0}; 

int no2serial[20];

int lastDescend[20];

serial은 노드의 전위 순회 순번을 의미하고

team[2]는 2번 노드의 팀을 의미하며 (int형이 아닌 bool형을 이용할 경우 속도가 많이 느려집니다.)

no2serial[2]는 2번 노드의 시리얼을 의미하고

lastDescend[2]는 2번 노드의 마지막 자손의 시리얼을 의미합니다.

다음은 전위 순회 코드입니다.

int serial=1;

void preorder(int noble) {

   no2serial[noble] = serial;

   serial++;

   for (int childn : child[noble])

       preorder(childn);

   lastDescend[noble] = serial-1;

   return;

}

먼저 시리얼은 전역 변수이고 노드 하나를 방문 할때마다 시리얼을 기억하고 1씩 증가합니다.

그리고 for문에서 재귀적으로 자식들을 방문합니다. (이런 형태의 for문은 C++10버전 이후부터 지원합니다.)

그렇게 1번 노드의 트리와 2번 노드의 트리를 모두 일직선상으로 만듭니다.

preorder(1);

preorder(2);

그럼 이러한 형태의 자료형이 되었습니다.

번호	1	19	12	3	16	6	4	9	15	8	2	14	10	18	11	7	17	5	13
serial	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
team	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
lastDescend	10	7	3	4	7	6	7	10	10	10	19	14	13	14	16	16	17	19	19

이제 배신을 재귀 순회 할 필요 없이 for문으로 할 수 있습니다.

void betray(int a) {

   for (int i = no2serial[a]; i <= lastDescend[a]; i++)

       team[i] ^= true;

}

betray(2)를 하여줍니다.

그러면 2번 노드와 그 모든 자손들이 배신을 하게 됩니다.

번호	1	19	12	3	16	6	4	9	15	8	2	14	10	18	11	7	17	5	13
serial	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
team	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1
lastDescend	10	7	3	4	7	6	7	10	10	10	19	14	13	14	16	16	17	19	19

이런 식이 됩니다. 그러면 배신 쿼리도 빠르게 할 수 있고

같은 팀 확인 쿼리도

team[no2serial[a]] == team[no2serial[b]] ?

printf("Ally\n") : printf("Enemy\n");

이런식으로 빠르게 할 수 있게 되었습니다.

여기까지만 해도 50000개 정도 노드 문제는 충분히 시간 내에 풀 수 있습니다.

팀 변수로 int배열대신 비트마스크를 사용할 경우 훨신 더 빠른 속도를 낼 수 있습니다. http://sunnyholic.com/89

하지만 여전히 주먹구구식을 최적화 하였을 뿐입니다. 50000이 아닌 그 이상의 경우에는 빠른 속도를 보장하지는 못할 것입니다.

여기서 3번 방법이 필요합니다.

접근법2

3. 배신 쿼리가 들어올때 해당 노드만 빠르게 배신한다. 같은 팀인지 체크는 빠르게 한다.

어떻게 이런 방법이 가능할까요? 구간합을 빠르게 구하는 이진인덱스트리를 사용하면 가능합니다. http://sunnyholic.com/90

이진인덱스트리는 구간합을 미리 계산해두어 해당 구간의 구간합을 빠르게 대답할 수 있게 합니다.

미리 계산해두었던걸 이용하기 때문에 계산했던것을 또 계산할 필요가 없지요.

이진 인덱스 트리를 BIT라고 합시다. BIT(20)으로 20개 노드를 다루는 트리를 생성합니다

BIT.add(no2serial[2],1) 하면 2번 노드에 1을 더하는 것이고

BIT.sum(no2serial[2]) 하면 0번 노드부터 2번노드까지 모든 값을 합한 값을 리턴하여줍니다.

트리를 생성하였으면

BIT.add(no2serial[2],1) 하여줍니다.

번호	1	19	12	3	16	6	4	9	15	8	2	14	10	18	11	7	17	5	13
serial	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
team	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
lastDescend	10	7	3	4	7	6	7	10	10	10	19	14	13	14	16	16	17	19	19

그러면 2번 노드부터 마지막 자손인 13번 노드까지 모두 BIT.sum(no2serial[n])을 하였을때 구간합이 홀수가 나오게 됩니다.

즉 짝수가 나오는 파란색 구간이랑 다른 팀임을 확인할 수 있는 것입니다.

이제 배신 함수를 구현하면 됩니다.

만약 16번 노드가 배신을 하였다면 BIT.add(no2serial[16],1)를 해주게 되는데

번호	1	19	12	3	16	6	4	9	15	8	2	14	10	18	11	7	17	5	13
serial	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
team	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	0	0	0
lastDescend	10	7	3	4	7	6	7	10	10	10	19	14	13	14	16	16	17	19	19

그러면 이런식이 되어버립니다. 자신(16)과 자기 자손들(6,4)의 팀만 바뀌여야 하는데 그 뒤 모든 노드들의 팀도 바뀌어 버렸습니다.

때문에 마지막 자손노드까지만 이 효과를 끊어주기 위해서 마지막 자손노드 뒤에 노드에도 1을 증가시켜 홀짝을 변경시켜 주어야 합니다.

즉 lastDescend[16]+1번 즉 시리얼 7+1번 노드에 1을 증가시켜 주는 것입니다. BIT.add(lastDescend[16]+1,1)

번호	1	19	12	3	16	6	4	9	15	8	2	14	10	18	11	7	17	5	13
serial	1	2	3	4	5	6	7	7+1	9	10	11	12	13	14	15	16	17	18	19
team	0	0	0	0	1	0	0	1	0	0	1	0	0	0	0	0	0	0	0
lastDescend	10	7	3	4	7	6	7	10	10	10	19	14	13	14	16	16	17	19	19

그러면 이런식으로 자기 자신과 자손들만 팀이 바뀌고 그 뒤는 유지되게 됩니다. 따라서 배신 함수는 이렇게 됩니다.

void betray(int a) {

    BIT.add(no2serial[a], 1);

    BIT.add(lastDescend[a] + 1, 1);

}

같은 팀을 확인하는 경우는 서로의 구간 합 값을 더해서 짝수가 나오면 같은팀 홀수가 나오면 다른팀이겠지요. 짝수+짝수는 짝수고 홀수+홀수는 짝수고 그 외는 홀수이니까요.

그래서 같은팀 확인은 이런식으로 하면 됩니다.

(BIT.sum(no2serial[a])+ BIT.sum(no2serial[b]))%2?

    printf("Enemy\n") : printf("Ally\n");

풀이 핵심

두가지 방법의 공통점 즉 전위 순회를 하며 트리를 일직선상으로 배치한다는 점과

전위순회를 하면서 마지막 자손 노드의 위치(즉 해당 노드를 루트로 하는 부분트리의 끝)를 기억한다는 점이 결국 공통된 부분으로

이 문제 풀이의 핵심이 됩니다.