BOJ 3311 - Traffic

팀원들과의 수 차례 논의 끝에 월파에서 메달을 따기로 했다. (의역 다수)

 

아직은 팀 내에서 자주 나오는 헛소리에 가깝지만, 메달까지는 아니더라도 이왕 힘들게 딴 티켓이 아쉽지 않도록 남은 기간 동안 공부를 열심히 할 것 같다. 나는 올해 리저널 (그리고 아마 Asia Pacific Championship도) 을 한 번 더 쳐야 하기도 하고..

 

내가 생각하기에 우리 팀.. 인지는 모르겠고 나의 문제는 한 문제에 대해 깊게 생각하지 못한다는 점이다. 아마도 PS 연습을 CP 위주로만 해서 그런 것 같은데, 이 부분에서 OI를 진지하게 판 사람들과의 차이가 벌어진다고 생각했다. 다이아 이상 문제에서 얻었어야 하는 능력이나 사고 과정이 부족한 느낌을 받을 때가 있다. 물론 주위에 OI를 열심히 한 사람이 없어서 진짜인지는 판단이 불가능하고 그냥 내 생각이 그렇다. 그래서 한동안은 한 번에 풀기 어려운 D2~D4 정도의 문제로 연습하려 한다. 뭐 풀면 좋고, 아니면 말고..

 

이왕 잡는거 퀄리티도 좋고 몇 문제 남지 않은 클10을 따고 시작하려 한다. 무슨 문제가 좋을까 둘러보다가 티어도 만만하고 평면 그래프니까 고급 알고리즘 시험공부라는 여러 이유로 이 문제를 잡게 되었다.

 

문제 요약

 

유향 평면 그래프 \(G\)가 주어진다. \(G\)의 모든 정점은 2차원 좌표평면 위의 격자점이며, \(0 \le x \le A, 0 \le y \le B\)를 만족한다. \(x = 0\)인 모든 정점에 대해 \(x=A\)인 정점 중 도달 가능한 것의 개수를 구하여라.

 

풀이

 

생각의 흐름

 

1) DAG에서 max, min이 아닌 더하는 식의 DP는 \(O(N^2)\)보다 빠르게 할 수 없다. 따라서 어떻게 빠르게 할지가 관건이 되겠다.

 

2) 일단 유향 그래프니까 SCC로 묶고 생각해보았다. 평면 그래프라 양 끝 변에 위치한 정점 사이의 관계가 적당히 단순하게 나온다는 방향으로 접근하려 했지만 가운데 있는 점과 사이클을 이룰 수 있기에 무산되었다. 여기 꽂혀서 시간을 조금 날렸다.

 

3) 시작/끝 정점들의 위치가 수직적이고, 평면 그래프라는 것은 뭔가 교차하지 않는다는 것이다. 따라서 일단 시작 정점을 고정하면 끝 정점의 $y$좌표가 구간을 이루지 않을까 생각했다. 허나 이런 경우 끝 정점 중 indegree가 0인 것들이 문제가 되었다. 그래서 아닌 줄 알고 시간을 또 조금 버렸다.

 

4) 아무리 생각해봐도 저런 접근 밖에는 되지 않아서 다시 돌아왔다. 다행히 끝 정점 중 indegree가 0인 것, 정확히는 어떤 시작 정점에서도 도달하지 못하는 정점을 날려준다고 생각하면 항상 성립하는 것 같았다. 마찬가지로 시작 정점 중 답이 0인 것은 쉽게 구할 수 있으니 없애고 시작한다.

 

5) 이러면 투 포인터를 하기 좋은 모양이 나온다. 시작 정점의 \(y\)좌표가 증가하면 끝 좌표의 최소/최대 \(y\) 좌표가 모두 증가한다는 뜻이다. 근데 뭔가 투 포인터나 이분 탐색을 얹으면 제곱이라 시간이 터진다.

 

6) 조금 고민을 해 봤는데, 아래서부터 훑으며 도달 가능한 끝 정점의 \(y\) 좌표 중 최댓값을 갱신해주고 / 반대 방향으로도 비슷하게 하면 될 것 같았다. 정점을 추가하며 DFS를 돌리는 식이라 하나당 \(O(N+M)\)에 가능하다.

 

7) 각 시작 정점에 대해 도달 가능한 끝 정점의 최소/최대 \(y\) 좌표를 구했다면 이분 탐색이나 투 포인터를 잘 써주면 답을 구할 수 있다. 다만 처음에 지운 정점은 고려하지 않아야 함에 유의하자.

 

구현은 뭔가 이쁘게 짜려고 노력하긴 했는데 잘 되지 않은 것 같다. 변수 이름을 헷갈려서 출력 초과도 3번 받았다.

 

시험 기간이라 그런 것인지는 모르겠지만, 그래도 오랜만에 시키는 대로 타자치는 국밥 자판기 역할이 아니라 생각하면서 문제를 푸는 경험을 하니 재미있었다.

 

풀고 팀원들한테 던졌더니 kwoncycle이 풀이를 잘 찾는 모습을 보여주었다. 더 열심히 해야겠다는 생각을 했다.