[BOJ] 24043. XOR 기계

starbow·2025년 4월 7일

PS/CP

목록 보기

20/25

$1$ 번 부터 $N$ 번까지 번호가 붙어있는 $N$ 개의 스위치가 있고 버튼을 누르면 기존에 표시된 수가 $X$ 일 때, $X \oplus A_i$ 로 변합니다. 우리는 최대한 서로 다른 수를 많이 만들어야 하고 방법이 여러가지라면 스위치를 최대한 적게, 그러한 방법도 여러가지라면 사전 순으로 가장 작은 방법으로 스위치를 누르는 방법을 찾아야 합니다.

먼저 각 수를 정점으로, 스위치 하나를 눌러 변경할 수 있는 수 사이를 스위치 번호로 라벨링한 간선으로 연결한 그래프 $G$ 를 생각해 봅시다. 그래프 $G$ 는 무방향 그래프로 생각해도 무방합니다. 어차피 $u = v \oplus A_i$ 라면 $u \oplus A_i = v$ 가 성립하기 때문입니다.

그리고 그래프 $G_x$ 를 정점 $x$ 에서 도달 가능한 모든 정점과 그러한 정점들 사이를 연결한 모든 간선들을 모아논 $G$ 의 부분 그래프로 정의 하겠습니다.

먼저 다음 내용을 증명해 보겠습니다.

Theorem. $G_0$ 는 BCC이다.

$G_0$ 의 임의의 정점 하나를 제거 해도 나머지 정점들 사이의 경로가 존재한다는 것을 보이면 됩니다. 이를 만족하지 않는 정점이 존재한다고 가정해봅시다. 해당 정점을 $v$ 라고 하면 서로 다른 두 정점 $u_1, u_2$ 가 존재하여 $u_1, u_2$ 사이의 모든 경로는 항상 $v$ 를 지나야 합니다.

\begin{aligned} u_1 \rightarrow \cdots \rightarrow v \rightarrow \cdots \rightarrow u_2 \end{aligned}

$v$ 의 이전과 이후의 정점은 $v \oplus A_i$ 형태임이 자명합니다.

\begin{aligned} u_1 \rightarrow \cdots \rightarrow v \oplus A_{i_1} \rightarrow v \rightarrow v \oplus A_{i_2} \rightarrow \cdots \rightarrow u_2 \end{aligned}

Case 1. $A_{i_1} = A_{i_2}$

이때는, 다음과 같이 경로를 수정할 수 있습니다.

\begin{aligned} u_1 \rightarrow \cdots \rightarrow v \oplus A_{i_1} \rightarrow \cdots \rightarrow u_2 \end{aligned}

Case 2. $A_{i_1} \neq A_{i_2}$

이때는, 다음과 같이 경로를 수정할 수 있습니다.

\begin{aligned} u_1 \rightarrow \cdots \rightarrow v \oplus A_{i_1} \rightarrow v \oplus A_{i_1} \oplus A_{i_2} \rightarrow v \oplus A_{i_2} \rightarrow \cdots \rightarrow u_2 \end{aligned}

각 케이스에 맞춰 경로에 있는 $v$ 를 제거해 가면 $v$ 를 지나가지 않는 경로를 만들 수 있습니다. 즉 모든 경로가 항상 $v$ 를 지난다는것에 모순이므로 증명이 완료되었습니다.

이제 다음 내용을 증명해 보겠습니다.

Theorem. $0$ 에서 시작하여 $G_0$ 의 모든 정점을 지나는 경로가 존재하며 최단 거리의 길이는 ( $G_0$ 의 정점 갯수) - 1 이다.

정점 $0$ 에서 간선 하나를 타고 다른 정점으로 이동한 다음 정점 $0$ 을 제거하는 상황을 생각해봅시다. $G_0$ 가 BCC이므로 정점 $0$ 을 제거해도 나머지 정점들 사이의 경로는 항상 존재합니다. 또한 정점 $0$ 을 제거한 이후에도 BCC를 만족합니다. 다시 말해 이 과정을 계속 반복하면 지나가지 않은 정점을 계속 지나가면서 $G_0$ 의 모든 정점을 지나갈 수 있습니다. 이걸로 증명이 완료되었습니다.

그럼 이제 최단 경로는 어떻게 찾을 수 있을까요? 그 중에서도 사전순으로 가장 작은 경로를 어떻게 찾을 수 있을까요? 두번째 정리의 증명을 잘 살펴보면 어렵지 않게 알 수 있습니다. $0$ 번 정점부터 간선의 라벨 번호가 가장 작은 번호부터 살펴보면서 DFS를 돕니다. 처음으로 다른 정점으로 이동하지 못했을 때, 사전순으로 가장 작은 최단 경로를 따라 이동을 마친것이므로 지나온 간선의 라벨을 순서대로 출력해주면 됩니다.