문제 링크
- http://icpc.me/3311
문제 출처
- 2011 CEOI Day2 3번
사용 알고리즘
- BFS/DFS
풀이
주어지는 그래프가 평면 그래프 라는 것에서 풀이가 출발합니다.
먼저 모든 왼쪽 정점에서 도달할 수 없는 오른쪽 정점을 지워주고, 도달할 수 있는 오른쪽 정점이 없는 왼쪽 정점도 지워준 상태에서 시작합시다.
그런 정점들은 신경 쓸 필요가 없이 0을 출력하면 됩니다.
주어진 그래프에서 BFS를 돌리고, 간선을 모두 뒤집은 다음에 BFS를 한 번 더 돌려주면 쉽게 처리할 수 있습니다.
필요 없는 정점들을 지워놓은 다음, 왼쪽 정점과 오른쪽 정점을 각각 y좌표 기준으로 정렬하고 보면 아래 3가지 성질을 알 수 있습니다.
가장 먼저, 왼쪽 정점에서 갈 수 있는 오른쪽 정점은 연속적입니다. 오른쪽 정점을 y좌표 기준으로 정렬을 합시다. 어떤 왼쪽 정점 L에서 $i ≤ j$일 때 i번째 오른쪽 정점과 j번째 오른쪽 정점을 모두 갈 수 있으면, L에서 $i ≤ x ≤ j$인 x번째 오른쪽 정점에 모두 갈 수 있습니다. 이것은 평면 그래프를 직접 그려보면 알 수 있습니다.
각 왼쪽 정점에서 갈 수 있는 오른쪽 정점의 y좌표 최댓값은 단조증가합니다.
위 그림에서 i번째 정점이 a부터 c번째 정점까지 갈 수 있으면, j는 c와 같거나 더 위에 있는 정점까지 도달 가능합니다.
귀류법을 이용해 단조 증가하지 않는다, 즉 j는 c와 c보다 위에 있는 정점에 갈 수 없다고 가정해보겠습니다.
j는 c를 못가고 c보다 아래에 있는 정점(a, b)만 갈 수 있다고 가정하면, i -> c의 경로와 j -> b의 경로에 교점이 생기게 됩니다.
문제에서 주어지는 그래프는 평면 그래프이기 때문에 교점이 발생하는 곳에 정점이 있을 수 밖에 없으며, 그 지점에 정점을 만들면 c에 갈 수 있게 됩니다.
각 왼쪽 정점에서 갈 수 있는 오른쪽 정점의 y좌표 최솟값은 단조감소합니다.
똑같이 증명할 수 있습니다.
도달 가능한 정점이 연속하다는 것도 관찰했기 때문에, 각 정점별로 upper_bound와 lower_bound만 잘 찾아주면 문제를 풀 수 있습니다.
각 왼쪽 정점마다 DFS를 돌려서 upper_bound와 lower_bound를 구할 것입니다. 그냥 돌리면 $O(V(V+E))$이기 때문에 시간 초과가 발생합니다.
우리는 위에서 upper_bound와 lower_bound가 단조롭다는 것을 관찰했기 때문에, DFS를 돌면서 방문한 정점을 굳이 다시 방문할 필요가 없습니다.
이 점을 활용해 lower_bound와 upper_bound를 각각 $O(V+E)$만에 구해줄 수 있습니다.