IOI 2021 Day 1

IOI 2021 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다.

한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.

• 반딧불, 100 / 67 / 70, 237점, 7등 - 11등
• 송준혁, 38 / 37 / 100, 175점, 28등 - 29등
• 장태환, 11 / 37 / 70, 118점, 71등 - 100등
• 최서현, 100 / 9 / 5, 114점, 102등

Day 1 만점자는 중국의 Mingyang Deng이 유일하다. 전체적으로 예년에 비해서 난이도는 어려운 편이다. 점수판을 보았을 때 올해는 세 문제에 난이도 차가 크게 없으며, 모두 10명 ~ 20명이 풀 수 있는 난이도의 문제로 준비된 것 같다. 특별히 쉬운 문제가 없어서, 학생들 입장에서는 상당히 당황스러웠을 것으로 보인다. 한국 학생들의 Day 1 성적은 예년 대비 평균적인 수준으로, 최종 대회에서 금메달을 딸 수 없을 정도로 점수차가 이미 많이 벌어진 학생은 없어 보인다.

구현한 풀이는 모두 https://github.com/koosaga/olympiad/tree/master/IOI 에서 찾을 수 있다.

문제 파일

candies-ISC.pdf

0.12MB

candies-KOR.pdf

0.15MB

keys-ISC.pdf

0.13MB

keys-KOR.pdf

0.17MB

notice-ISC.pdf

0.12MB

notice-KOR.pdf

0.16MB

parks-ISC.pdf

0.15MB

parks-KOR.pdf

0.19MB

문제 1. 사탕 분배

서브태스크 1 (3점)

사탕의 개수를 배열에 저장한 후 문제에서 요구하는 사항을 구현하면 된다. 시간 복잡도는 $O(NQ)$ 이다.

서브태스크 2 (11점)

사탕을 쌓기만 하니 박스가 빌 걱정을 하지 않아도 된다. 또한, 사탕이 용량을 초과하는 문제점은 매 쿼리마다 해결할 필요가 없다. 모든 쿼리를 처리한 후에 용량을 초과하는 사탕을 빼 줘도 무방하다.

고로, 구간에 특정 수를 더하는 쿼리를 여러 번 처리하면 문제를 해결할 수 있다. 이는 여러 가지 방법으로 해결할 수 있는데, 가장 간단한 방법은 변홧값 배열이다. 이 기법에 대해서는 인터넷에 좋은 설명이 많으니 검색해 보기 바란다. 시간 복잡도는 $O(N+Q)$ 이다.

서브태스크 3 (38점)

$C_i$ 가 일정하기 때문에, 구간에 다음 두 연산을 적용할 수 있으면 된다.

• $A_i := A_i + X$
• $A_i := min(A_i, Y)$

이를 지원하는 자료구조를 고안하는 문제로, 여기서 크게 두 가지 풀이를 알고 있다.

첫 번째 풀이는 사전지식을 사용하는 풀이이다. Segment Tree Beats라는 자료구조가 위 두 연산을 지원한다. 본인은 이 글과 이 동영상을 보고 Segment Tree Beats를 익혔던 것 같다. 둘 다 좋은 자료이니 한번 보는 것을 추천한다. 위 자료구조를 알고 있으며 구현에 익숙하다면 날로 먹기 아주 좋은 풀이이다.

두 번째 풀이는 여기에 조금 더 아이디어를 사용한다. 구간에 적용하는 함수의 꼴을 $f(x) =max(C, min(x - A, B))$ 형태로 표현하면, $f(g(x))$ 역시 $max(C, min(x - A, B))$ 형태로 나옴을 계산할 수 있다. 이를 사용하면 구간에 함수를 적용시키는 문제가 되니 $f(x)$ 를 Lazy propagation으로 관리할 수 있게 된다. 아마 이런 아이디어에서 출발하면 서브태스크 4의 풀이도 나온다고 (그리고 결론적으로 전체 문제가 sqrt 시간에 풀린다고) 들었다.

만점 풀이

만점 풀이는 그다지 어려운 자료구조를 사용하지 않는다. 다만 오프라인 쿼리라는 점을 적극적으로 활용하며, 발상의 전환을 요구한다.

수열에다가 쿼리를 적용한다고 생각하지 않고, 쿼리의 결과에서 숫자를 찾아낸다고 생각하자. 예를 들어서, $N = 1$ 이라고 하였자. 쿼리로 $+v[1], v[2], +v[3], -v[4]$ 형태의 수들이 들어왔을 때, 이것들을 직접 시뮬레이션하지 않고도 $A[1]$ 의 최종 결과를 알 수 있는 방법이 있을까? 만약 이 $A[1]$ 의 결과를 예쁘게 표현할 수 있다면, 전체 문제는 $A[i]$ 의 인덱스가 증가하는 순서대로 스위핑하면서 풀 수 있다.

• 각 쿼리에 대해서 "현재 쿼리가 가지고 있는 $v[j]$" 값을 저장한다. 초기에는 전부 0이다.
• $i$ 에서 $i+1$ 번 점으로 넘어갈 때, 시작점이 $i + 1$ 인 쿼리들의 $v[j]$ 값을 입력으로 주어진 값으로 설정한다.
• 반대로, 끝점이 $i$ 인 쿼리들의 $v[j]$ 는 0으로 맞춰줘서 실질적으로 지워버린다.

이렇게 할 경우, 배열에 $O(Q)$ 번의 변화만으로 현재 가지고 있는 쿼리의 리스트를 시간순으로 관리할 수 있다. 만약 $A[1]$ 의 최종 결과가 세그먼트 트리등으로 관리 가능한 값이라면, 매 지점마다 적절한 쿼리로 답을 구할 수 있으니 전체 문제가 효율적으로 해결될 것이다. 이제 목표는, 세그먼트 트리로 관리하기 쉬운 형태로 $A[i]$ 의 최종 결과를 표현하는 것이다.

이러한 문제는 일반적으로 각 수의 변화 형태를 그래프로 그리면 좋다. 쿼리 시간을 $x$ 축, 값을 $y$ 축으로 하고 값의 그래프를 그려보자. 이 때, 문제의 조건과 상관없이, 값이 0 미만으로 떨어지거나 $C[i]$ 를 넘는 것은 고려하지 않고, 그대로 현재까지 들어온 값의 합만 그래프로 그려주자. 즉, 그래프는 $(i, \sum_{j = 1}^{i} v[j])$ 점들을 잇는 꺾은 선이다.

일단 $C[i]$ 가 무한히 크다고 가정하고 관찰해보자. 만약 $C[i]$ 가 무한히 크다면, 현재 배열의 값은 $\sum_{j = 1}^{q} v[j]$ - (그래프 상 최저점의 $y$ 좌표) 이다. 최저점에 도달했을 때는 무조건 0개의 사탕이 있는데, 그 이후로는 사탕이 바닥나는 일은 없기 때문이다. $C[i]$ 가 적당히 작더라도, 만약에 그래프 상 최고점과 최저점의 높이 차가 $C[i]$ 이하라면, 동일한 논리가 성립한다.

만약 두 점의 높이차가 $C[i]$ 초과라면 어떻게 될까? 일단, 그래프 상에서 최고점과 최저점의 높이 차가 $C[i]$ 이하로 유지되는 가장 긴 suffix를 찾은 후, 이 suffix의 바로 왼쪽 값을 넣어주자. 이 경우, 가장 왼쪽 값을 넣으면 suffix의 높이 차는 $C[i]$ 초과, 안 넣으면 $C[i]$ 이하가 된다. 만약

• 가장 왼쪽 값이 최댓값이라면: 현재 배열의 값은 $\sum_{j = 1}^{q} v[j]$ - (구간 상 최저점의 $y$ 좌표) 이다. 최저점에 도달했을 때는 무조건 0개의 사탕이 있기 때문이다.
• 가장 왼쪽 값이 최솟값이라면: 현재 배열의 값은 (구간 상 최대점의 $y$ 좌표) $- \sum_{j = 1}^{q} v[j]$ 이다. 최고점에 도달했을 때는 무조건 사탕이 가득 차 있기 있기 때문이다.

이제 전체 문제는 세그먼트 트리를 사용하여 해결할 수 있다. $v[j]$ 의 prefix sum을 값으로 가지는 세그먼트 트리를 만들고, 각 노드에 대해서 구간 최댓값과 최솟값을 관리하자. 먼저, 최고점과 최저점의 높이 차가 $C[i]$ 이하로 유지되는 가장 긴 suffix는 이분 탐색을 통해서 $O(\log^2 N)$ 에 찾거나, 트리를 타고 내려가면서 $O(\log N)$ 에 찾을 수 있다. 이 점을 찾은 후에는, 그냥 이 점과 그 왼쪽을 시작점으로 하는 Suffix의 최댓값 / 최솟값만 구해주면 최종 값을 판별하는 데 필요한 모든 정보를 얻을 수 있다.

갱신된 시점에는, 어떠한 Suffix에 특정한 값을 더한 후 위 두 값을 관리해야 한다. 이는 Lazy propagation을 사용하면 된다. 총 시간 복잡도는 $O((N + Q) \log N)$ 이다.

서브태스크 4 풀이와 Sqrt decomposition

사실 본인은 서브태스크 4의 풀이를 모른다. 들었던 방향성은, 서브태스크 3에서 볼 수 있듯이 $C$ 가 고정되면 쿼리 적용 이후의 함수가 3개 정도의 정수로 표현 가능하며, 여러 개의 $C$ 에 대해서도 이 함수를 스택 등으로 열심히 비비면 잘 구할 수 있다는 내용이었다. 더 자세히 알아보고 싶으면 이런 글을 보면 될 것 같다. 시간 복잡도는 $C$ 의 정렬을 제외하면 $O(N + Q)$ 로 보인다.

확실한 것은, 서브태스크 4를 $O(N + Q)$ 정도에 처리할 수 있으면 전체 문제도 $O((N + Q)\sqrt Q)$ 정도에 처리할 수 있다. 쿼리를 $\sqrt Q$ 조각으로 쪼개서 처리하자. 쿼리가 $\sqrt Q$ 개라면, 전체 배열을 각 구간에 적용되는 쿼리의 집합에 따라서 $2\sqrt Q$ 개의 구간으로 나눌 수 있다. 이 구간 각각을 $O(len + \sqrt Q)$ 에 처리하면, $\sqrt Q$ 개의 쿼리가 $O(N + Q)$ 에 처리된다. 이를 $\sqrt Q$ 번 반복하면 전체 문제가 $O((N + Q) \sqrt Q)$ 시간에 처리된다.

반딧불 학생과 김동현 코치가 이러한 식으로 해결했다고 한다. 다만 Sqrt를 사용하기 때문에 어느 정도 효율적인 구현은 필요해 보인다.

이 아이디어에 멋진 자료구조를 추가하면 $O(Q \log^2 N)$ 에 온라인으로도 풀 수 있는 것 같다.

문제 2. 열쇠

서브태스크 1 (9점)

37점까지는 p[i]의 최소를 구한다 가 아니라 모든 p[i]를 구한다 고 생각해도 문제가 풀린다. 여기서도 이러한 식으로 접근한다.

만약 현재 방에 0번 열쇠가 없다면, 답은 1이다. 그렇지 않다면, 답은 해당 방에서 도달 가능한 방의 개수이다. 이는 DFS로 계산할 수 있다.

서브태스크 2 (20점)

각 $i$ 에 대해서 따로 문제를 해결한다. 매 순간 현재 도달 가능한 정점 집합 $S$ 를 관리하고, $S$ 의 크기를 하나씩 늘리는 것을 시도해 볼 수 있다.

• 현재 $S$ 에 있는 모든 키의 종류를 배열에 마크한다.
• $S$ 에 인접하며, $S$ 에 있는 키로 도달 가능한 다른 정점 하나를 골라, $S$에 넣는다. 그러한 정점이 없으면 그대로 종료한다.

이를 반복하면 각 $i$ 에 대해서 문제가 $O(nm)$ 에 해결되며 전체 문제는 $O(n^2m)$ 에 해결된다.

서브태스크 3 (37점)

위 과정을 큐를 사용하여 최적화한다. 너비 우선 탐색을 사용하고, 추가적으로 "현재까지 발견된 키", "현재까지 발견되지 않은 키로 들어갈 수 있는 정점" 리스트를 관리한다. 새로운 정점을 방문하였을 때, 이 정점에서 새로운 종류의 키를 발견했다고 하자. 그렇다면 지금까지 해당 키가 없어서 들어가지 못했던 정점 리스트를 바로 다 방문할 수 있으니, 전부 큐에 넣어준다. 이 정점에서 인접한 정점을 현재까지 발견한 키로 방문할 수 있다면 큐에 넣어주고, 아니면 나중에 해당 키를 받았을 때 바로 들어갈 수 있도록 리스트에 쌓아둔다.

만점 풀이

서브태스크 4만 푸는 풀이는 잘 모르겠다. 주위에서도 알아낸 사람이 없고, 데이터가 약하다는 제보 정도만 조금 있는 것 같다. 뭐가 됐든 만점 풀이와는 큰 상관이 없지 않나 싶다.

정점 $v$ 에서 $r[v]$ 번 키를 사용하여 다른 정점에 방문할 수 있다면, 이러한 정점 중 하나 (여럿일 경우 아무거나) 를 $w(v)$ 라고 하자. $w(v)$ 가 도달할 수 있는 정점들은 모두 $v$ 에서 도달할 수 있음을 알 수 있다. 다른 말로, $S_{w(v)} \subseteq S_v$ 이다. 만약 그러한 정점이 없다면 $w(v) = v$ 라고 하자.

이제 $v \rightarrow w(v)$ 로 간선을 이어주자. 이러한 그래프의 각 컴포넌트는 사이클 하나를 루트로 한 트리 형태를 한다는 것이 잘 알려져 있다. 각 간선은 집합의 포함 관계를 나타내니, 한 사이클에 묶여있는 정점들은 서로가 서로를 포함하는 관계고 이들 간에는 도달할 수 있는 정점들의 집합이 같다. 고로, 이들을 하나의 정점으로 묶어서 생각할 수 있다. 이 정점들이 가진 키, 그리고 이 정점에서 인접한 다른 정점들을 모두 하나로 합쳐주면, 사이클의 크기가 항상 2 이상이니 정점의 개수가 줄어든다. 이렇게 새롭게 합쳐진 정점에서도 위와 같이 $w(v)$ 를 정의하자. 이 때 키는 하나가 아니고 여러 개라는 것이 차이점이다.

이렇게 줄어든 그래프에서도 문제를 푸는 것을 반복하면, 더 이상 길이 2 이상의 사이클이 생기지 않는 (다른 말로, 사이클에서 도달할 수 있는 새로운 정점이 없는) 시점이 생기게 된다. 이 때, 각 트리의 루트를 제외한 정점들은, 모두 트리의 루트를 방문할 수 있다. 하지만 트리의 루트에서는 자신을 제외한 정점을 방문할 수 없다. 고로, 트리의 루트만이 유일한 답의 후보가 되며, 루트에서 도달할 수 있는 정점의 수는 단순히 해당 정점에 합쳐졌던 초기 정점의 집합이니, 쉽게 계산할 수 있다. 만점 풀이의 아이디어는 이것이 끝이고, 이를 Naive하게 구현하면 $O(nm)$ 정도의 시간이 걸릴 것이다.

이제 이 과정을 최적화하자. 최적화를 할 때는 특별히 문제의 성질에 대해서는 관찰할 필요는 없고, 효율적인 자료구조를 고민하는 것으로 충분하다.

• 사이클을 찾는 것은 Union-find를 통해서 해 줄 수 있다.
• 합쳐진 정점을 관리하는 것은 또 다른 Union-find를 통해서 해 줄 수 있다.
• 두 정점을 합칠 때 키와 인접 리스트를 합쳐줘야 하는데 이는 Small-to-large를 통해서 해 줄 수 있다.
• 새로운 정점을 만들었을 때 $w(v)$ 를 빠르게 찾아야 한다. 리스트를 관리할 때 인접한 간선들 중 현재 가진 Key들로 도달이 가능한지 아닌지 를 기준으로 집합을 두 조각으로 나누자. 두 집합을 합쳐줄 때, 작은 쪽에서 새롭게 들어온 Key들을 넣으면서 리스트를 조정할 수 있다. 이 부분은 어느 정도 Naive하게 해 줘도 되는 것이, 한 간선은 도달이 불가능한 상태에서 가능한 상태로 바뀌지 그 반대로 되지는 않기 때문이다. 이걸 키 단위로 조금 나이브하게 합쳐주는 것이 67점 풀이일지도 모르겠다.
• 아무튼 도달이 가능한지 불가능한지의 여부로 간선 집합을 분리했으니, 집합에서 아무 간선이나 뽑으면 $w(v)$ 를 찾을 수 있다. Self-loop만 아니면 되는데, Self-loop인지는 Union-find로 확인해 보고, 맞으면 지워버리면 된다.

시간 복잡도는 $O(M \log^2 N)$ 이다. 여담으로, 본인은 알고리즘이 Directed MST를 구하는 효율적인 알고리즘과 비슷하다는 느낌을 많이 받았다. 이번 기회에 한번 공부해 보는 것도 좋을 것 같다.

문제 3. 분수 공원

서브태스크 2 (15점)

문제를 크게 두 가지 부분으로 나눌 수 있다.

• 공원의 분수를 잇는 스패닝 트리가 있는지 찾고, 있다면 만드는 것
• 스패닝 트리의 각 도로에 대해 서로 다른 벤치를 매칭할 수 있는지 찾는 것

(이 글에서는 스패닝 트리의 간선을 "도로" 라고 부른다. 간선에 간선을 매칭한다 같은 혼란스러운 표현을 막기 위해서이다.)

스패닝 트리를 만드는 방법이 여러 가지가 있고, 이 중 어떤 방법을 택하는지에 따라서 두 번째 부분이 어려워 질 수 있다. 일단은, 아무 스패닝 트리나 잡아도 매칭을 할 수 있다고 믿음을 가진 후 문제를 해결해 보자.

아무 스패닝 트리나 찾는 방법은 다음과 같다. 전체 점을 $(x, y)$ 좌표 순서로 정렬한 후, 정렬 순서상에서 인접한 두 점의 거리가 2인 경우 도로를 이어준다. 반대로 $(y, x)$ 좌표 순서로 정렬한 후 똑같이 해 주면, 모든 가능한 도로의 후보가 나온다. 이제 이 그래프에서 Union-find 등으로 아무 스패닝 트리나 찾아주면 된다. 만약 그래프가 연결이 아니라면 여기서 -1을 반환하면 된다.

스패닝 트리의 각 도로에 벤치를 매칭하는 방법을 살펴보자. 이 서브태스크에서는 상당히 간단한 방법으로 벤치를 매칭할 수 있다. 벤치의 가능한 위치를 $x = 1, x = 3, x = 5$ 로 나눈 후, $x = 1$ 은 왼쪽 세로 도로, $x = 3$ 은 가로 도로, $x = 5$ 는 오른쪽 세로 도로에 매칭할 것이다. 왼쪽 세로 도로는 중점에서 왼쪽으로 한 칸 움직인 위치에 벤치를 두고, 오른쪽 세로 도로는 중점에서 오른쪽으로 한 칸 움직인 위치에 벤치를 두고, 가로 도로는 중점에서 위로 한 칸 움직인 위치에 벤치를 두자. 이 방법을 사용하면, 아무 스패닝 트리를 찾아도 항상 벤치를 매칭시켜줄 수 있다.

서브태스크 4 (35점)

서브태스크 4에서는 가능한 스패닝 트리가 유일하다. 스패닝 트리는 대충 찾고, 벤치 매칭만 최적으로 신경써서 해 주면 된다.

스패닝 트리를 구하고, 각 도로에 인접한 벤치들을 모두 구해주자. 각 도로에 대해서 정확히 두 개의 벤치와 매칭을 해 줄 수 있을 때, 모든 도로를 벤치와 매칭하는 문제가 된다.

이는 전형적인 이분 매칭으로, $O(N^2)$ 시간에 문제를 해결할 수 있다. 하지만 이는 비효율적이다. 효율적으로 문제를 해결하기 위해서는 각 도로가 정확히 두 개의 벤치 와 매칭된다는 사실을 활용해야 한다. 벤치를 정점으로 하고, 각 도로가 매칭되는 두 벤치 사이에 간선을 잇자. 우리가 해결해야 하는 문제는, 이 그래프의 각 간선에 서로 다른 정점을 매칭해 주는 문제이다. 이 문제는 선형시간에 해결할 수 있는데,

• $V < E$ 인 컴포넌트가 있으면 매칭이 불가능하다.
• $V - 1 = E$ 인 경우는 그래프가 트리이다. 아무 정점을 루트로 잡자. 모든 간선에 대해서, 루트에서 멀어지는 쪽의 정점을 매칭한다. 이 경우 모든 간선이 서로 다른 정점에 매칭되며 루트는 매칭되지 않는다.
• $V = E$ 인 경우 그래프에 사이클이 정확히 하나 존재한다. 사이클 상의 아무 간선을 잡은 후, 양 정점 중 아무 곳에나 매칭한다. 매칭한 간선을 지우고, 매칭에 들어있는 정점을 루트로 한 트리에서 위 알고리즘을 활용하여 매칭을 구해준다.

서브태스크 3/5 (70점)

서브태스크 4를 구현하면 70점까지 받는 것은 어렵지 않다. 아마 35점을 받을 의도로 구현했다 하더라도 55점 / 70점을 받았을 가능성이 높다. 풀이를 살펴보자.

• 서브태스크 5의 경우, 스패닝 트리를 어떻게 구해도 각 벤치에 인접한 도로가 최대 2개이다. 위에서 매칭을 구한 그래프로 생각하면, 모든 정점의 차수가 최대 2라는 것이다. 이 경우 그래프의 각 연결 컴포넌트는 트리 혹은 사이클이라서, $V \geq E$ 가 항상 만족하고, 매칭이 항상 존재한다.
• 서브태스크 3의 경우는 웬만한 스패닝 트리가 반례가 되지 않는다. 예를 들어, 세로 선분을 우선으로 하고, 남으면 아래에 있는 가로 선분부터 넣는 식으로 스패닝 트리를 구성하자. 이렇게 구현할 경우 AC가 나오고, 반례도 제한 안에서는 없는 것으로 보인다. 좋은 풀이는 아니지만, 굳이 엄밀히 따질 것 까지는 없어 보인다.

서브태스크 5의 간단한(?) 풀이 (55점)

만점 풀이를 소개하기 앞서, 서브태스크 5를 풀 수 있는 다른 풀이를 소개한다. 이 풀이는 서브태스크 5의 성질을 조금 더 자연스럽게 사용하며, 매칭을 따로 구해줄 필요가 없다. 사실 그렇게 간단한 풀이인지는 모르겠지만, 이 풀이를 이해해야 만점 풀이로 넘어갈 수 있다.

벤치를 중심으로 하는 2x2 정사각형 하나를 셀 이라고 부르자. 문제에서 주어진 평면을 셀 로 분할할 수 있으며. 도로는 셀과 셀 사이의 경계를 보여준다.

모든 셀 을 Chessboard와 같이 흑백으로 칠한다. 이 중 검은 셀은 가로 도로 를 담당하고, 하얀 셀은 세로 도로 를 담당한다. 서브태스크 5에서는, 각 벤치에 인접한 가로 도로가 최대 하나고, 세로 도로도 최대 하나이다. 검은 셀에 가로 도로가 인접하다면 둘을 매칭하고, 하얀 셀에 세로 도로가 인접하다면 둘을 매칭하자. 모든 가로/세로 도로에 대해서, 인접한 검은/하얀 셀이 무조건 존재하니, 이렇게 매칭하면 모든 도로를 셀에 매칭할 수 있다. 이렇게 하면 스패닝 트리를 구할 필요도 없고, 매칭도 구할 필요도 없이, 바로 문제가 해결된다.

만점 풀이

위와 같이 모든 셀을 흑백으로 칠하는데, 이번에는 검은 셀에 가로 도로가 2개 인접할 수도 있고, 하얀 셀에 세로 도로가 2개 인접할 수도 있다. 각 셀에서 둘 중 적절한 도로를 하나 골라서, 그래프가 여전히 연결되게끔 구성해야 한다.

다음과 같은 알고리즘을 생각하자:

• 검은 셀에 가로 도로가 2개 인접하면 상단 가로 도로를 고른다. 1개 인접하면 상하 상관없이 그 하나를 고른다.
• 하얀 셀에 세로 도로가 2개 인접하면 좌측 세로 도로를 고른다. 1개 인접하면 좌우 상관없이 그 하나를 고른다.

이후 선택된 도로들을 반환한다. 이게 풀이의 끝이고, 이를 구현하면 만점을 받는다.

이제 알고리즘을 증명하자. 이 알고리즘에서 각 셀은 항상 서로 다른 도로를 고르게 된다. 고로 선택된 도로들이 연결되었음만 증명하면 된다. 들어가기 앞서, 분수들이 5x5 그리드일때 어떠한 도로들이 선택되는지를 그림으로 살펴보자.

이제 알고리즘을 증명한다.

정점을 셀 + 외곽의 무한한 면 (Outer face) 으로 하고, 인접한 두 셀이 고르지 않은 도로로 분리되어 있으면 간선을 그어주자. 이 그래프에 단순 사이클이 없으면, 전체 그래프가 연결되어 있다. 있으면, 그래프가 연결되어 있지 않다. (이는 Dual Graph의 성질로, Cut-Cycle Duality라고 부른다). 이 사이클이 Outer face를 포함한다고 하고 (그렇지 않은 경우도 동일하다), 사이클에 속한 간선을 ${e_1, e_2, \ldots, e_k}$ 라고 하자.

일반성을 잃지 않고 $e_1$ 이 가로 간선이며, 또 사이클이 아래에서 위로 올라오는 방향으로 형성되어 있다고 하자, 이 경우, $e_1$의 아래는 하얀 셀, 위는 검은 셀이어야 한다. 위가 검은 셀인데 아래가 뚫렸다는 것은, 이 셀의 모서리에 모두 분수가 있다는 뜻이다. 고로 위쪽/오른쪽 길이 막혀 있으며, 왼쪽으로 움직여야 한다. 왼쪽이 하얀 셀인데 오른쪽이 뚫렸다는 것은, 이 셀의 모서리에 모두 분수가 있다는 뜻이도다. 고로 아래/왼쪽 길이 막혀 있으며, 위로 움직여야 한다. 이 논리를 무한히 반복하면, 분수의 개수가 유한하다는 가정에 모순이다.

그림으로 그리면 대충 이렇다.

요약하자면, 저렇게 대각선으로 체인이 날아가는 트리를 그려주어서 항상 매칭이 존재하는 그래프를 만들 수 있다. 이렇게 보면 결론은 참 간단하지만, 풀기는 상당히 어려운 문제라고 생각한다. 후기를 들어보면 스패닝 트리를 때려맞추는 것도 나름대로 승산이 있는 것 같은데, 적당한 휴리스틱으로 데이터를 뚫어보는 것도.. 할 게 없다면 해 볼만한 전략인 것 같다.