BOJ 16964 - DFS 스페셜 저지

링크: https://www.acmicpc.net/problem/16964

풀이

문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다.

올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.

이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다.

위 그림처럼 입력이 주어졌다고 해보자.

여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.

2번째 순서인 3번 노드는 자신의 서브트리 크기 4만큼 다음인 2+4번째(6번째) 순서인 4번 노드와 형제이다.

3번째 순서인 5번 노드는 자신의 서브트리 크기 2만큼 다음인 3+2번째(5번째) 순서인 6번 노드와 형제이다.

하지만, 전부 형제인 것은 아니다.

7번째 순서인 7번 노드는 9번째 순서인 2번 노드와 형제가 아니다.

다시 돌아가서, 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다고 말한 적이 있다.

형제 노드가 있어야 할 자리가 나보다 더 낮은 깊이(트리의 레벨)이면 된다는 뜻이다.

크기가 1인 노드를 제외하고 이를 위반하는 경우가 있다면 0을, 전부 만족한다면 1을 출력하면 정답니다.

각 정점의 깊이와 자식의 수를 처음에 DFS를 한번 실행해서 구한 후, 각 정점마다 위 규칙을 만족하는 지 확인하면 된다.

코드