IOI 2023 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.

박상훈, 43 / 60 / 65.5 / 31 / 100 / 54, 353.5점, 22등 (금메달)
이동현, 52 / 70 / 65.5 / 31 / 100 / 16, 334.5점, 28등 (금메달)
이성호, 43 / 40 / 61 / 23 / 65 / 35, 267점, 58등 (은메달)
반딧불, 43 / 60 / 65.5 / 14 / 65 / 16, 263.5점, 62등 (은메달)

금메달 2개, 은메달 2개로 평균 이상의 성적을 거두었으며, 작년과도 동일한 성적이다. 축하합니다!

Day 1은 전례가 없이 어려웠는데, Day 2도 만만치 않게 어려운 문제들이 나왔다. 2018 Day 2와 유사한 결과가 나왔으니, 전례는 있는 정도의 어려움이라고 할 수 있겠다. 그런 점에서 쉬운 문제를 풀고 침착하게 Robot의 점수를 올리면 다른 학생 비해 유리한 고지를 점할 수 있는 대회이기도 하다. 올해의 우승자는 중국의 Tingqiang Xu 학생 이다. 작년과 동일하게 최근 중국의 최상위권 학생들은 Codeforces 랭킹 등에서 일찍이 두각을 보이고 있고 올해도 예외가 아니다. 그 전과 같이 1/2/3/4 등을 모두 차지하지는 않았으나, 이번 대회를 통해 최근 중국의 선전이 우연한 결과가 아님을 엿볼 수 있다. 축하합니다!

구현한 코드는 https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

Day 2 Problems PDF

robot-KOR.pdf

1.04MB

overtaking-KOR.pdf

0.34MB

beechtree-KOR.pdf

0.42MB

robot-ISC.pdf

0.86MB

overtaking-ISC.pdf

0.23MB

beechtree-ISC.pdf

0.31MB

Problem 4. 참나무

서브태스크 1-4 (31점)

공통적으로 필요한 관찰은 딱 하나 있다.

어떠한 노드 $v$ 에 대해 $S(v)$ 를 $v$ 의 자식과 $v$ 를 잇는 노드들의 색상 수열이라 하자. $S(v)$ 에 중복된 원소가 존재한다면, $v$ 를 포함하는 서브트리는 아름다울 수 없다.

위 조건을 처리하고, 남은 노드들에 대해서만 문제를 해결한다고 가정했을 때, 각 서브태스크는 아래와 같이 해결할 수 있다.

서브태스크 1은 모든 순열을 전부 시도해 보면 된다.
서브태스크 2는 순열의 경우가 단 하나라 조건만 확인해 보면 된다.
서브태스크 3의 경우, 루트의 자식들을 degree가 감소하는 순서대로 정렬하자. 그 순서를 $v_1, v_2, \ldots, v_k$ 라고 했을 때, $S(v_1) \supseteq S(v_2) \supseteq \ldots \supseteq S(v_k)$ 가 성립함과 서브트리가 아름답다가 동치이다.
서브태스크 4의 경우, 아름다운 순열 하에서 모든 노드의 부모가 $0$ 혹은 $1$ 이다. 고로, 서브태스크 4의 조건을 만족하고 답이 존재한다면, 트리의 깊이가 2 이하이다. 이는 서브태스크 3과 동일하다.

이러나 저러나 만점 풀이에는 크게 도움이 안 되는 서브태스크들이다.

서브태스크 5 (45점)

서브태스크 3의 풀이는 "특정한 방식으로만 아름다운 순열을 만들어도 되어서, 조건을 빠르게 판별할 수 있다" 라는 맥락에 기반해 있다. 만점으로 가는 방향도 이와 동일하며 그럴 것이라 생각하기도 어렵지 않으나, 결국 그 특정한 방식 이 무엇인지가 핵심이 될 것이다.

한 가지 Naive한 접근은 서브태스크 3의 방법을 그대로 사용해서, $S(v_1) \supseteq S(v_2) \supseteq \ldots \supseteq S(v_k)$ 가 성립하는 순열이 존재하는가를 확인하는 것이다. 일단 아름다운 순열은 위 조건을 무조건 만족하는 것이 사실이지만, 위 조건만으로 충분치 않다는 것은 예제 3을 통해서 확인할 수 있다. 이 조건이 성립해도 답이 없을 수 있는 이유를 조금 더 구체적으로 생각해 보면, $S(v_1) = S(v_2)$ 인 노드가 존재할 때 $v_1$ 보다 $v_2$ 가 늦게 들어갔다면, $v_1$ 의 서브트리 역시 $v_2$ 의 서브트리보다 먼저 등장해서 $v_1$ 을 일찍 택해야 하는 식으로, 재귀적으로 논리가 계속 이어지기 때문임을 알 수 있다. 이 논리의 끝은 둘 다 모두 빈 서브트리거나 (우열이 없음) 아니면 한 쪽 트리가 비는 (우열이 있음) 상황일 것이다. 이를 정리하면 다음과 같은 결론이 나온다:

Theorem 1. 어떤 트리가 아름답다는 것은, 다음 조건을 만족하는 순열 $v_1, v_2, \ldots, v_n$ 이 존재함과 동치이다: 모든 $1 \le i < n$ 에 대해, $T(v_i)$ 에서 리프를 지우는 연산을 $0$ 회 이상 반복하여 $T(v_{i+1})$ 을 얻을 수 있다.

Proof of $\rightarrow$. $T(v_i)$ 에서 $0$ 회 이상 리프를 지워 $T(v_j)$ 를 얻을 수 있음을 $i \rightarrow j$ 라고 하자. 이 연산은 transitive하기 때문에, $i \rightarrow j, j \rightarrow k$ 면 $i \rightarrow k$ 이다. 즉, 위 명제는 임의의 $i < j$ 에 대해서 $i \rightarrow j$ 가 성립한다는 것과 동치이다.

아름다운 트리에는 아름다운 순열이 존재하며, 그 순열이 정확히 위 조건을 만족함을 증명한다. 트리 노드들의 번호를 아름다운 순열에 맞춰 relabel했다고 하고, 수학적 귀납법을 $i$ 가 감소하는 순서대로 사용한다.

$i = n$ 일 때는 자명하다.
$i < n$ 일 때, $i+1$ 의 각 자식 $ch(i+1, c)$ 에 대해, 이에 대응되는 $i$ 의 자식 $ch(i, c)$ 가 존재하며, 또한 $ch(i, c) < ch(i+1, c)$ 임을 아름다운 순열의 구성에 따라 알 수 있다. 귀납 가정에 따라 각 서브트리에 대해 $ch(i, c) \rightarrow ch(i+1, c)$ 가 성립하니 $i \rightarrow i+1$ 역시 성립한다.

Proof of $\leftarrow$. 트리 노드들의 번호를 위 순열에 맞춰 relabel 하고 $0, 1, \ldots, n-1$ 순서로 트리를 구성하자. 이 과정에서 처음으로 구성한 트리가 틀리는 시점을 생각해 보자. 즉, $i$ 번 노드의 부모로 $f(i)$ 를 추가했는데, 실제로 $f(i)$ 가 기대하던 자식이 $i$ 번 노드가 아니라는 것이다. 지금 우리가 트리에 노드를 삽입하는 것은 서브트리 크기가 최대인 순서대로 삽입하니, 이 경우 $f(i)$ 가 기대하던 자식은 $i$ 에서 $1$ 회 이상 리프를 지워 얻을 수 있는, 더 작은 트리일 것이다. 또한, 내가 실제로 들어가야 했었을 부모 역시, $f(i)$ 보다 번호가 큰 어떤 노드일 것이다 ($f(i)$ 가 원래 기대하던 자식은 같은 부모 간선 색을 가지기 때문에, 실제 카운트가 증가). $f(i)$ 와 $p_i$ 를 두고 보았을 때, $f(i) < p_i$ 인데, $ch(f(i), c) \nrightarrow ch(p_i, c)$ 이니, 가정에 모순이다.

Theorem 1의 조건은 DP를 통해서 파악할 수 있다. $DP[i][j]$ 를 $i \rightarrow j$ 가 성립하는가로 정의하면, $S(i) \supseteq S(j)$ 이며, 모든 $c \in S(j)$ 에 의해 $DP[ch(i, c)][ch(j, c)]$ 가 성립한다면 $DP[i][j]$ 는 참이 된다. 이 DP는 $O(n^2)$ 에 계산할 수 있다. 모든 서브트리의 원소에 대해, $i \rightarrow j, j \rightarrow i$ 가 성립하면 아름다운 순열이 존재하니, 모든 정답을 $O(n^3)$ 에 파악할 수 있다.

서브태스크 7 (71점)

사실 서브태스크 5에서 제시한 풀이를 조금만 고쳐도 71점까지 얻을 수 있는데, 어차피 저런 식으로 만점을 받기는 어렵다. 5의 조건은 아래와 같이 표현하면 훨씬 더 간단하게 표현할 수 있다:

Theorem 2. 어떤 트리가 아름답다는 것은, 다음 조건을 만족하는 순열 $v_1, v_2, \ldots, v_{n}$ 이 존재함과 동치이다. 모든 $1 \le i < n$ 에 대해:

$|T(v_i)| \geq |T(v_{i+1})|$
$ch(v, c)$ 를 $v$ 와 $c$ 색의 간선으로 연결된 자식이라고 하자. 모든 $x \in S(v_{i+1})$ 에 대해, $|T(ch(v_i, c))| \geq |T(ch(v_{i+1}, c))|$

Proof sketch. 조건 자체가 동치는 아니다. 그렇게 하면 반례가 있고, 이걸 만족하는 순열이 있어야 동치이다. 그래서 증명을 그대로 쓰진 못하고 따로 해야 하는데, Theorem 1의 증명을 이 조건 하에서 동일하게 해 주면 동치임을 알 수 있다.

이제 문제를 해결하는 것은, 트리의 노드들을 상술한 기준으로 정렬한 후, 모든 인접한 노드들에 대해 위 조건이 만족하는지를 확인하는 것이다. 사실 첫 번째 조건은 두 번째 조건에서 함의되는 것이라, 그냥 두 번째 조건만 확인해 주면 된다. $A_v[c] = |T(ch(v, c))|$ 라는 수열을 생각해 보면, 결국 위 정의는 $A_v$ 라는 수열을 사전 순 역순으로 정렬한 후 확인하면 됨을 알 수 있다. 길이 $M$ 의 수열을 직접 만들지 않고 $c$ 를 기준으로 정렬된 인접 리스트를 순회하면, 사전 순 비교가 가능하고, 여기부터는 std::sort 를 써도 충분하다. 서브트리 크기 정도만 전처리 해 두면 $O(n^2 \log n)$ 정도에 문제가 해결된다.

만점 풀이

71점 풀이를 위와 같은 방식으로 얻었다면, 이를 만점 풀이로 최적화 하는 것은 경험 많은 참가자들에게 쉬운 일이다. 순열을 std::set 과 같은 BST에 정렬된 순서대로 저장한 후, 서브트리에 대한 순열들을 small-to-large 로 합쳐주고, 합쳐주는 과정에서 삽입한 노드의 양옆으로 인접한 노드들 간에 위 조건이 깨지는지를 확인해 주면 된다.

차수가 큰 노드들간의 비교를 반복적으로 하면 복잡도가 깨질 수 있다고 걱정할 수 있으나, 비교의 복잡도가 $\min(deg(u), deg(v))$ 이고, 한 노드는 최대 $\log n$ 번 삽입되니, 복잡도 면에서 문제가 생기지 않는다. $O(n \log^2 n)$ 에 전체 문제가 해결된다.

Problem 5. 추월

서브태스크 3 (39점)

$t_{i, j}$ 에 대한 정의가 모두 주어져 있고, 이걸 구하는 방법이 문제 지문에 아주 구체적으로 적혀있다. 고로 지문에 적혀 있는 것을 정렬 등을 사용하여 그대로 구현하면 된다. 시간 복잡도는 $O(QNM \log N)$ 이다.

서브태스크 4 (65점)

문제에서 가장 중요한 관찰은 나보다 빠른 버스는 없는 버스나 마찬가지 라는 것이다. 절대 나의 움직임에 영향을 줄 수 없기 때문이다. 이는 다른 버스들에게도 마찬가지이다. 예를 들어 입력에서 가장 느린 버스의 경우 항상 자신의 속도에 맞게 주행할 수 있다. 그 다음으로 느린 버스는 해당 버스에 대해서만 영향을 받고, 그 다음은 앞 두 버스에만... 이런 식이다. 이러한 관찰을 하면, 예제 설명에 나와 있는 예쁜 그림을 그릴 수 있고, 이 그림을 따라서 각 버스의 도착 위치도 빠르게 구할 수 있다.

$W[i] \le X$ 인 버스들은 입력에서 모두 무시해 주고, $W[i]$ 가 큰 순서대로 버스들을 고려하자. 첫 번째 버스가 추월 장소에 도착하는 시간은 모두 결정된다. 두 번째 버스도 그렇게 오다가, 만약 앞에 첫 번째 버스가 있다면 이 버스에 맞춰 속도를 늦춘 후 다시 진행한다. 이를 시뮬레이션하기 위해서는 $i-1$ 번째 추월 장소와 $i$ 번째 추월 장소 사이, 각 버스의 시작 시간 / 끝 시간을 적당한 자료 구조에 저장하자. $i$ 번째 버스의 시작 시간보다 나중에 출발한 버스가 내 앞을 가로막는다면, 이 버스의 도착 시간이 내 도착 시간이고, 아니면 내 원래 도착 시간이 도착 시간이다. 이렇게 하면 시작 시간과 도착 시간이 단조적으로 증가하니, 그 적당한 자료구조 는 std::set 같은 BST로 충분함을 알 수 있다.

이렇게 하면 $O(NM \log N)$ 정도에 예비 버스를 제외한 모든 버스들의 운행 궤적을 알 수 있다. 쿼리가 주어질 때는, 그냥 위 방법과 똑같이 하되 삽입만 안 하면 된다. 고로 각 쿼리는 $O(M \log N)$ 정도에 해결이 된다.

모든 입력된 $W[i]$ 에서 $X$ 를 빼고, 나의 속도를 무한히 빠르다고 가정한 후, 답에 $XL$ 을 더하면 구현이 간단하다. 만점 풀이에서는 이것을 했다고 가정한다.

만점 풀이

추월 장소가 아닌 곳에서 다른 버스를 추월할 수 없다. 고로 내가 추월 장소를 넘어갔다면, 그 이후 나의 도착 시간은 적어도 내 바로 앞에 있는 버스 이상이다. 고로 각 추월 장소 사이에 있는 버스는 대략 현재 시간에 다음과 같은 역할을 한다고 볼 수 있다:

$x > s_i$ 일 경우, $x = \max(x, e_i)$ 를 적용한다.

각 추월 장소마다 이것을 추월 장소에 도착하는 시간 역순으로 나열하면, 이제 단순 자료 구조 문제가 된다. $NM$ 개의 구간 $[s_i, e_i]$ 가 주어질 때, 쿼리로 주어진 $x$ 들에 대해서 위 연산들을 순서대로 적용하고, 그 결과를 출력하는 문제가 되는 것이다. 이 문제를 해결할 수 있는 방법이 여러 가지 있지만, 여기서는 그 중 가장 구현이 단순한 방법을 소개한다.

$f(x)$ 를 $x$ 가 주어졌을 때 결과적으로 얻는 반환값을 나타내는 함수라고 하자. 맨 처음, $f(x) = x$ 이고, 이 함수를 연산을 적용하는 역순으로 수정한다. 이는, $x \in (s_i, e_i]$ 구간에 대해 $f(x) = \max(f(x), f(e_i))$ 를 적용하는 것과 동일하다.

여기까지만 해도 사실 세그먼트 트리로 그대로 구현할 수 있지만, 함수 개형을 관찰하면 더 단순한 풀이를 얻을 수 있다. 매 쿼리가 주어질 때마다, 함수는 $(s_i, f(e_i))$ 라는 점을 아래에 포함하게끔 위로 올라간다. 고로, 함수가 꺾이는 점 에 대한 단조 체인을 std::set 으로 관리하면,

$f(x_i)$ 개별의 쿼리를 얻는 것은, $x < x_i$ 인 최소 꺾이는 점의 $y$ 좌표를 구하는 것으로 가능하다.
꺾이는 점 하나가 추가되면, $x$ 좌표가 이것 이상, $y$ 좌표가 이것 이하인 점들을 모두 제거해야 한다.

이렇게 하면 $O(NM \log NM)$ 시간에 함수 개형을 전부 관리할 수 있고, 각 쿼리는 위에서 설명한 대로 대답하면 된다. 전체 문제는 $O((NM+Q)\log NM)$ 시간에 해결된다.

Problem 6. 로봇 대회

서브태스크 1 (6점)

오른쪽에 경계가 있으면 아래로 가고, 없으면 오른쪽으로 가면 된다.

서브태스크 2 (16점)

무조건 오른쪽으로 가다가, 장애물이 보이면 아래/위로 피해서 가고, 그러다가 도착 점이 $(0, W - 1)$ 이면 거기서 아래로 가면 된다.

서브태스크 3 (34점)

문제에 나와 있는 Display Tool이 매우 유용하다. 구현 시 이 도구를 무조건 사용하는 것을 추천한다.

이 문제는 주어진 그리드에서 최단 경로를 찾는 문제이기 때문에, DFS / BFS 와 같은 탐색 기법을 사용한다고 생각할 수 있다. 일반적인 그리드에서는 BFS를 사용하여 최단 경로를 찾으니, 만점 풀이 역시 BFS를 구현할 것으로 추정되지만, 처음부터 시도하기에는 다소 어렵다. 서브태스크 3/4는 특수한 형태의 그리드가 주어지기 때문에 조금 더 간단한 방법을 생각해 볼 수 있다.

서브태스크 3은 주어진 그리드가 트리 형태를 띈다. 트리에서 경로를 탐색하는 것은 DFS로 가능하며, 특히 부모 정점의 번호를 저장하는 식으로 중복 방문을 쉽게 막을 수 있다는 점에서 일반적인 DFS보다 더 간단하다.

이를 문제의 상황에 맞게 다음과 같이 구현할 수 있다. 각각의 점에 대해 다음과 같이 상태를 배정하자:

$0$: 초기 빈 셀
$3, 4, 5, 6$: 현재 해당 셀 아래를 탐색 중이며, 탐색중인 방향이 서,남,동,북 임

현재 셀에 $0$ 이 적혀있다면, 격자의 $(0,0)$ 점이거나 아니면 부모에서 이동하여 방문했을 것이다. $(0, 0)$ 점이면 남쪽부터 탐색을 시작하기 위해 $4$ 를 적고, 색칠된 부모가 있다면, 부모의 시계 반대방향으로 인접한 방향에서 탐색을 시작하기 위해 이에 대응되는 수를 적자.

이제 현재 셀에는 $3, 4, 5, 6$ 과 같은 방향 중 하나가 적혀있다. 이 방향의 셀을 보았을 때

만약에 해당 방향의 셀이 장애물이라면, 방향을 시계 반대방향으로 돌리고 그대로 종료하자.
만약에 해당 방향의 셀이 $3, 4, 5, 6$ 으로 색칠되어 있다면, 부모 방향이다. 즉, 이 방향에서 탐색이 종료되었으니, $0$ 으로 칠하고 부모로 올라가자.
만약에 해당 방향의 셀이 $0$ 이라면, 이 방향으로 내려가면서 탐색한다. 이 때 현재 셀의 방향을 시계 반대방향으로 돌려 주어야 한다 (이후 중복 방문을 막기 위함)

이 과정을 통해서 끝점에 도달했다면, 현재 색칠된 셀이 정확히 시작점에서 끝점으로 가는 경로에 일치하는 것을 볼 수 있다. 이제 이 셀들을 $1$ 로 칠해주기만 하면 된다. 이는 끝점을 $1$ 로 칠하는 것으로 시작한 후, 색이 칠해진 방향으로 반복적으로 움직이면서 $1$ 을 칠해주면 된다. $1$ 은 탐색이 끝난 이후에만 등장하는 색이니, 위의 탐색 과정에서 $1$ 이 인접한 수에 발견된다면 예외 처리를 추가해서 현재 셀을 $1$ 로 칠하고 $3, 4, 5, 6$ 이 칠해진 다른 셀로 움직이는 것을 반복하고 시작점에서 종료하면 된다.

서브태스크 4 - 부분 점수 (44점)

서브태스크 4에서는 최단 경로가 $W+H-2$ 의 길이를 가지는 것이 보장되는데, 이는 다시 말해 최단 경로는 동쪽 / 남쪽으로만 이동해도 찾을 수 있다는 것이다. 동쪽 / 남쪽으로 이동해서 도달할 수 있는 어떤 경로도 최단 경로가 되니, 서브태스크 4도 DFS로 해결할 수 있다.

일반적으로 트리가 아닌 그래프에서 DFS를 하면 visited 체크를 해서 중복 방문을 막는 처리를 한다. 전체 점수를 얻기 위해서는 이 체크를 풀어주기까지 해야 하지만, 부분 점수를 얻는다면 체크를 해 놓고 그대로 두어도 된다. 이 정도는 위에서 제시한 서브태스크 3 풀이를 몇 글자만 수정해도 가능하다. 두 가지만 고치자:

셀의 방문을 포기하고 돌아갈 때 이 셀을 비우지 않고 "방문함" 체크를 한 후, 이 체크가 된 셀은 장애물과 동일하게 간주하기
서 / 북 쪽으로 탐색하지 않기

서브태스크 4의 전체 점수를 얻기 위해서는 이후 visited 체크를 모두 해제해 줘야 한다. 이는 visited가 되어 있는 점을 빈 점으로 간주하는 식의 DFS를 한번 더 돌리면 가능하다. 만점 풀이의 방식과는 큰 상관이 없어 자세히 설명하지는 않는다.

서브태스크 5 - 부분 점수 (80점)

서브태스크 3/4가 DFS를 시뮬레이션하면 해결되는 것처럼, 만점 풀이는 BFS를 시뮬레이션하면 해결할 수 있다. 이렇게 얘기하면 간단해 보이지만, 일반적인 BFS 구현에 사용되는 Queue를 사용할 수 없어서 아이디어가 필요하다.

핵심 아이디어는, 시작점에서 거리가 $d$ 이하인 모든 점들을 포함하는 BFS Tree가 주어질 때, 이를 거리가 $d+1$ 이하인 모든 점을 포함하는 BFS Tree로 확장하는 작업을 반복하는 것이다. 이렇게 하면 서브태스크 3과 같은 트리 구조의 이점을 사용할 수 있어 편리하다.

이를 위해서는 모든 리프에 대해서, 해당 리프에 인접한 노드들을 BFS 트리에 넣고 종료하는 프로시저가 필요할 것이다. 즉, 주어진 BFS Tree를 탐색하는 알고리즘이 필요하다. BFS Tree의 표현은, 루트 노드가 아닌 노드에 대해서 부모 방향을 $3, 4, 5, 6$ 으로 표현하고, 루트 노드는 $2$ 로 표현하는 식으로 설정하자.

맨 처음에, 루트 노드를 $2$ 로 설정하고, 탐색을 시작한다. 현재 노드의 상태가 $2$ 라고 하자. 인접한 노드 중 BFS Tree 상의 자식이 있다면, 이 자식 방향으로 반복적으로 내려가면서 탐색을 진행한다. 이 과정에서 루트로 가는 경로는 모두 $2$ 로 색칠된다.

이제 BFS Tree 상의 자식이 없는 상태에 도달했다고 하자. 정확히 현재 노드의 인접한 노드만을 트리에 추가해야 한다. 일단 현재 노드를 $1$ 로 칠하여, 다른 리프 노드와 구분한다. 이후 인접한 모든 $0$ 인 노드들을 $1$ 을 부모로 가지도록 색칠하고, 과정을 끝낸다.

과정을 끝나면 이제 $1$ 인 현재 노드에서 나와서, 부모로 올라간 다음 다시 자식 노드들을 찾아야 할 것이다. 이를 위해서 현재 노드를 $3, 4, 5, 6$ 으로 바꿔야겠지만, 이럴 경우 부모 노드에서 이미 방문한 노드와 그렇지 않은 노드를 구분하지 못한다는 문제가 있다. 이 노드를 $0$ 으로 바꿔주고, 부모로 올라가자.

부모 노드 입장에서 이 과정이 종료되면, 원래 있던 자식 하나가 $0$ 이 된다. 여전히 남은 자식이 있다면, 부모 노드는 이 자식을 방문할 것이고, 방문한 후 이 노드도 $0$ 이 될 것이다. 그렇다면, 부모 노드는 $2$ 가 적혀 있고, 모든 자식이 $0$ 이 된 상태에 도달한다. 이는 리프의 상태와 동일하다. 고로, 부모 노드에 $1$ 을 적은 이후 자식들의 상태를 모두 복원하고, 그리고 자신은 $0$ 으로 바뀐 채로 또 부모의 부모로 올라간다. 이 과정을 반복하면, 트리의 모든 노드를 중복 없이 방문하면서, 또 트리의 구조를 그대로 유지할 수 있다.

마지막에 자신이 $0$ 이 되었는데 루트라서 부모가 없다면, $2$ 를 적어주면 된다. 이러면 트리의 크기만 $d+1$ 로 확장된 상태에서 정확히 시작 상태로 되돌아 가며, 초기 시작 상태 역시 예외처리 없이 표현할 수 있다.

이 과정을 하면서 도착점을 발견하였다면, 이제 답을 출력하면 된다. 트리의 경우가 그랬듯이, $2$ 를 따라가면서 이를 $1$ 로 바꿔주는 것을 반복하면 된다. 위 탐색 과정에서는 $2$ 의 근처에 $1$ 이 있을 수 없는데, 경로를 따라 올라갈 때는 $2$ 의 근처에 무조건 $1$ 이 존재한다. 고로 현재 $2$ 가 쓰여 있을 때, 이것이 최종 출력용인지 탐색용인지는 주위 $1$ 의 존재 여부로 명확히 구분할 수 있다.

만점 풀이

거리 $d$ 에 있는 도착점을 발견한 순간, 그리드에는 거리 $d$ 이하의 거의 모든 정점이 포함된 BFS 트리가 기록되어 있다. 이 BFS 트리를 사용하면 적힌 다른 값들을 청소 하는 것을 구현할 수 있다.

다만 다음과 같은 예외가 있다.

아직 방문하지 않은 거리 $d$ 의 정점 몇 개. 사실 이들은 전혀 문제가 되지 않아 이후 언급하지는 않는다.
방문하면서 도착점을 찾지 못해서 0으로 바꿔두고 온 정점들.

일단 예외가 없다고 생각하면, $2$ 를 따라가면서 $1$ 로 바꾸는 과정에서 $3,4,5,6$ 이 적힌 서브트리로 내려간 후 이들을 지워주면 된다. 위 알고리즘에서는 $3,4,5,6$ 을 발견하면 탐색 모드라고 생각하여 $2$ 를 적는다. 이 $2$ 는 루트로 가는 경로를 이루니, 만약 인접한 정점에 $2$ 가 없다면 탐색 모드가 아니라 청소 모드라고 생각할 수 있다. 고로 $2$ 인 노드를 방문한 이후 다음과 같은 식으로 청소를 하면 된다:

$2$ 가 적혀 있고 $1$ 이 인접하면 $2$-청소 모드로 인식한다. $2$-청소 모드에서는 $2$ 를 $1$ 로 바꾼다.
$1$ 이 적혀 있고 $1$ 이 인접하면 $1$-청소 모드로 인식한다. $1$-청소 모드에서는 주위에 있는 $3,4,5,6$ 을 발견하여 그 쪽으로 움직인다. 움직이는 목적은 해당 서브트리를 모두 $0$ 으로 지우는 것이다. 없으면 근처에 있는 $2$ 로 올라가거나 종료한다.
$3,4,5,6$ 이 적혀 있고 $2$ 가 인접하지 않으면 $3,4,5,6$-청소 모드로 인식한다. $3,4,5,6$-청소 모드에서는, 리프가 아닌 경우 리프로 내려가고, 리프인 경우 $0$ 으로 값을 비워둔 후 부모로 다시 올라가는 식으로 재귀적으로 청소를 구현해 준다.

이를 구현하면 위 예외 상황을 제외하고 모든 정점을 지운다. 이제 위 예외를 처리하는 건 간단한데, 그냥 $2$-청소 모드에서 인접한 위치에 $0$ 이 있으면, 80점 풀이와 같은 방식으로 모두 다 자식으로 만들어주고 오면 된다. 어차피 $0$ 으로 바꿔둔 정점들은 모두 $2$ 에 인접하며 실제로 이 $2$ 를 부모로 가졌기 때문에, 이런 식으로만 해 줘도 모든 서브트리를 다시 붙일 수 있다. 이를 구현하면 만점을 받을 수 있다.

IOI 2023 Day 2

댓글