문제
https://www.acmicpc.net/problem/10521
해설
노드와 스위치가 있는 기계에 공을 굴려보냈을 때, 각 노드의 스위치 상태를 구하는 문제입니다. 노드들의 연결 상태는 DAG(Directed Acyclic Graph) 형태로 주어지고, 스위치의 상태에 따라 인접한 노드 중 왼쪽이나 오른쪽으로 공이 통과합니다. 1개의 공이 노드를 통과할 때마다 스위치의 상태가 반전됩니다.
구현
한 노드에 공이 몇 개 통과하는지 알면, 스위치가 어떤 상태가 되는지 알 수 있습니다. 만약 어떤 노드에 k개의 공이 통과한다면
- i) k가 짝수일 때, 왼쪽과 오른쪽으로 k/2개씩 분배됩니다. 스위치의 최종 상태는 변하지 않습니다.
- ii) k가 홀수일 때, 초기상태에 따라 왼쪽과 오른쪽으로 k/2+1개와 k/2개가 분배됩니다.(초기 방향으로 +1) 스위치의 최종 상태는 반전됩니다.
따라서 1번 노드부터 n개의 공을 위상정렬 순서로 좌우 노드들에게 분배해주면 됩니다.
노드에 통과하는 공의 갯수는 indegree와 무관하게 계속 누적하되, Queue에는 indegree가 0일 때(마지막 한번)만 push해줍니다.
시간복잡도 계산
위상 정렬의 시간복잡도는 O(V+E)입니다. 여기서 V는 노드의 갯수 m이고, 노드당 좌우로 2개의 간선이 있으므로 E는 2m입니다. 이므로 위상 정렬을 사용하여 제한시간 내에 해결할 수 있습니다.
소스 코드
http://boj.kr/9b625de451b74c278d3f8698e898901d