BOJ 18189 - 참 어려운 문제

12월의 마지막 날에 쓴 화풀이 글 이후로 처음 쓰는 블로그 글이다. 1달 동안은 PS를 거의 하지 않았다. Hello BOJ 떨 때문도 있고, 연습시킨다고 모은 동아리 사람들의 참여율이 저조해 준비할 맛이 잘 안나서 그것도 던졌다. 그 결과 코포랑 앳코더도 많이 걸렀고, 백준도 그냥 브론즈로 스트릭만 채우고, 버추얼도 하기로 했었는데 상황이 잘 맞지 않아 몇 번 못했다.

 

그 와중에 일은 잔뜩 벌여놔서 문제를 내야할 일이 굉장히 많았다. 하루 종일 연구실에 앉아서 읽으라는 논문은 안 읽고 문제 낼 생각만 하는데, 어째 내가 생각한 문제들은 다 구데기인 것 같다.. 좋은 문제들을 좀 보면 아이디어가 떠오를 수도 있다고 생각해 어렵고 좋은 문제들을 좀 풀어 보려 한다.

 

주로 클래스 문제들이나 국내 최고의 인재들이 문제를 내는 설곽, 경곽, 서울대, 카이스트 교내대회 문제들을 좀 돌아보려 한다. 어떻게 그런 퀄리티의 문제들을 매년 뽑아내는지 신기할 따름이다. 물론 다른 좋은 문제 추천도 환영입니다.

 

오늘 푼 문제는 유명한 문제들이 꽤 있는 19년도 경곽 송년대회 셋의 18189 - 참 어려운 문제이다. 문제 상황이 정말 간단하면서 보편적인데, 풀이가 깔끔하면서 어렵다. 정말 좋은 문제라고 생각한다. 나는 똑똑한 방법을 몰라 무식한 방법으로 풀었다.

 

우선, 모든 색에 대해 루트로 가능한 정점을 구하면 해당하는 정점들의 교집합이 정답이 된다. 따라서 색을 고정하고 생각해보자. 색을 고정했을 때 루트로 가능한 정점이 존재함은 일직선상에 존재하는 세 색칠된 정점이 없음과 동치이다.

 

어떤 정점을 루트로 삼았을 때 두 색칠된 정점이 조상-자손 관계가 아님이 문제의 조건인데, 만약 세 색칠된 정점이 일직선상에 있다면 어떤 정점을 루트로 삼아도 두 정점은 조상-자손 관계가 된다. 만약 이러한 세 정점이 없다면 루트로 가능한 정점의 영역이 생긴다. 어떠한 세 색칠된 정점도 일직선상에 있지 않다는 것은 색칠된 정점을 포함하는 가장 작은 스패닝 트리가 색칠된 정점들은 리프로 하는 성게 그래프와 같은 형태를 띈다는 것이며, 루트로 가능한 정점의 영역은 성게 그래프에서 색칠된 정점으로 막히지 않도록 flood fill을 한 모양과 같을 것이다.

 

 

그림이 좀 발퀄이지만, 위 설명에서 나타난 형태는 트리에서 두 가지 형태로 나타난다. 하나는 색칠된 정점을 루트로 하는 서브트리 밑에 나타나는 형태, 다른 하나는 색칠되지 않은 정점을 루트로 하는 서브트리 밑에 나타나는 형태이다. 당연히 두 형태 모두 색칠된 정점은 모두 리프여야 한다. 검은색을 색칠된 정점, 빨간색이 루트로 가능한 정점의 영역이라 할 때 왼쪽 그림이 전자, 오른쪽 그림이 후자이다.

 

이를 판단하기 위해 출제자님은 트리 압축이라는 테크닉을 쓰시는데, 나는 몰라서 오일러 투어 트릭과 세그트리로 박치기를 도전했다. 우선 색칠된 정점이 두 형태 중 하나인지 판별해보자. 아니라면 0 0 0을 출력하고 종료하면 된다. 각 색에 대해 세그트리와 DFS 넘버링을 통해 색칠된 정점에 +1을 해주자. 그리고 각 색칠된 정점을 루트로 하는 서브트리에 색칠된 정점이 몇 개 있는지로 왼쪽과 오른쪽을 구분할 것이다. 색칠된 정점의 총 개수를 \(C\)라 할 때 왼쪽은 1, 1, 1, 1... C 형태여야 하고, 오른쪽은 1, 1, 1, ... 1 형태여야 한다. 이러면 후자는 판별이 끝나는데, 전자는 한 가지 과정을 더 거쳐야 한다. 색칠된 정점이 ㅅ자 모양으로 있다면 배열은 1, 1, 2가 나오지만 세 정점이 일직선상에 있기 때문에 불가능하다. 이러한 경우를 거르려면 왼쪽 경우에서 가장 위에 있는 색칠된 정점에 대해 다른 모든 정점이 한 자식 밑에 있는지 추가로 검사해주어야 한다.

 

이제 경우를 나누었으니 가능한 영역에 체크를 해야 한다. 이는 추가적인 누적합 배열 또는 세그먼트 트리와 오일러 투어 트릭을 이용하면 된다. 전자는 루트가 되는 색칠된 정점의 자식 아래를 모두 체크하고 리프가 되는 색칠된 정점의 아래에 다시 -1을 더하면 되며, 후자는 1번 정점 아래를 모두 체크하고 리프 아래에 -1을 더하면 된다.

 

이 모든 과정을 거치고 모든 색에서 체크된 정점들을 구해주면 된다.

 

나의 조악한 풀이 말고도 멋있고 깔끔한 풀이들이 많으니 모두 풀어보셨으면 좋겠다.

 

새벽에 써서 풀이 상태가 좀 조악한데.. 열심히 쓰려고 노력했으니 피드백 주시면 감사하겠습니다.