BOJ 25015. 아이싱

문제 링크

15685B+alpha를 짜고 풀었다. 지금까지 해본 다양한 문제풀이들 중에서도 기억에 남을 정도로 힘들었던 것 같다. 자력솔한 문제 중에서는 최소 3위 안에 드는 것 같다. 해싱을 쓰는 쉬운 풀이가 있다고 하니 구현할 생각이 있다면 그쪽 풀이를 써 보도록 하자.

 

문제를 요약하면 다음과 같다.

• 그래프 $G$에서 간선 $k$개를 지워서 이분 그래프로 만들 수 있는 $k$의 최솟값 $k_{min}$이 $2$ 이하인지 판정한다.
• $k_{min}$이 $2$ 이하라면, 그래프 $G$에서 $k_{min}$개의 간선을 지워 이분 그래프로 만드는 경우의 수를 출력한다.

접근 방식

이 문제에서는 $k_{min}$이 $0$, $1$, $2$인지 각각에 대해서만 판정하면 된다. 따라서 $k_{min}$의 값이 이들 중에 있는지 알아내는 것이 우선순위가 될 것이다.

 

그 다음으로는 각 $k_{min}$의 값에 따라 경우의 수를 구하는 알고리즘을 설계해야 한다.

 

결론적으로, $k=0$, $1$, $2$ 각각의 값에 대해 $k$개의 간선을 지워 이분 그래프를 만들 수 있는지 판단하고, 만약 가능하다면 그 경우의 수를 구하면 될 것이다.

$k=0$

$k=0$인지를 판단하는 것은 주어진 그래프가 이분 그래프인지를 판단하는 것과 같다. 이것은 DFS를 이용해 $O(N+M)$ 시간에 판정할 수 있다. 간선을 하나도 지우지 않으므로, 경우의 수는 물론 $1$이다.

$k = 1$

$k=1$인지를 판단하는 것은, 주어진 그래프에서 간선 하나를 제거해 이분 그래프가 될 수 있는지를 판단하는 것과 같다. 만약 가능하다면, 제거할 수 있는 간선의 개수를 구해야 한다.

 

먼저 임의의 정점을 시작점으로 잡은 뒤 DFS를 돌릴 것이다. back edge를 제거한 형태의 DFS spanning tree를 $T$라고 하고, back edge의 집합을 $S$라고 하자. $S$에서 두 끝점 $(u, v)$가 트리에서 짝수 거리만큼 떨어진 간선 $(u, v)$는 홀수 사이클을 만드는 데 기여한다. (이러한 $(u, v)$ 쌍이 없었다면 $k_{min} = 0$이었을 것이다.) 이러한 back edge만을 모아 놓은 집합을 $S_{odd}$라고 하고, 그렇지 않은 back edge들의 집합을 $S_{even}$이라고 하자. (즉, $S_{odd}$의 간선들은 홀수 사이클을, $S_{even}$의 간선들은 짝수 사이클을 만든다.)

 

이제 각각의 간선에 대해, 해당 간선을 제거했을 때 이분 그래프가 되는 경우 그 간선을 좋은 간선이라고 하자. 먼저 다음을 간단히 관찰할 수 있다.

• $S_{odd}$의 간선(back edge)이 좋은 간선이 되기 위해서는 $\left| S_{odd} \right| = 1$이여야 하고, 이때 $S_{odd}$ 내의 유일한 간선은 좋은 간선이 된다.
  • 증명: $S_{odd}$에 두 개 이상의 간선이 있는 경우, 어떤 back edge를 자르더라도 남은 back edge로 인해 홀수 사이클이 생긴다. 따라서 $S$에 간선이 하나 있는 경우에만 back edge가 좋은 간선이 될 수 있다.

이제 트리 간선이 좋은 간선인지의 여부를 판정할 수 있어야 한다. 먼저 다음 사실이 자명하다.

• 트리 간선이 좋은 간선이라면, 해당 간선은 $S_{odd}$ 내의 임의의 간선 $(u, v)$에 대해, 트리 $T$ 위에서 $u$와 $v$를 잇는 경로 상에 존재해야 한다.

또한 다음 사실을 추가로 관찰할 수 있다.

• 어떠한 트리 간선이 $S_{even}$의 임의의 간선 $(u, v)$에 대해, 트리 $T$ 상에서 $u$와 $v$를 잇는 경로 상에 포함된 경우, 해당 간선은 좋은 간선이 아니다.
  • 이 간선을 사용한 사이클은, 이 간선을 사용하지 않는 짝수 사이클의 여집합 부분으로 대체할 수 있다.

위 두 관찰로부터, 다음과 같이 트리 간선 $(p, x)$가 좋은 간선이 될 조건을 정리할 수 있다.

• $S_{odd}$ 내의 모든 간선 $(u, v)$에 대해, 간선 $(p, x)$는 $T$ 위에서 $u$와 $v$를 잇는 경로에 포함된다.
• $S_{even}$ 내의 모든 간선 $(u, v)$에 대해, 간선 $(p, x)$는 $T$ 위에서 $u$와 $v$를 잇는 경로에 포함되지 않는다.

이제 우리는 위 두 조건을 만족하는 모든 간선 $(p, x)$가 좋은 간선임을 보일 것이다. 이분 매칭, 홀수 사이클과 관한 주제가 나올 때 생각하면 좋은 것은 bipartite coloring이다. 즉, 정점들을 기우성에 따라 흑/백으로 색칠한다고 생각한다. 이때 인접한 정점이 다른 색으로 색칠되어야 한다. Bipartite coloring의 가능성은 그래프가 이분 그래프라는 사실과 동치이다.

 

그리고, 위 조건을 만족하는 간선 $(p, x)$를 잘랐을 때, 우리는 남은 그래프에서 bipartite coloring이 가능함을 보일 수 있다. 방식은 간단한데, 먼저 $p$와 $x$를 같은 색으로 칠하고, 트리 $T$의 간선들만을 보고 남은 정점들을 bipartite coloring 한다. (트리는 이분 그래프이므로 이것이 항상 가능하다.) 이제 $S$의 간선들의 양끝점이 서로 다른 색의 정점으로 칠해졌음을 보이면 된다. 그런데, $S_{even}$에 속한 간선의 경우 정점이 $p$ 쪽 서브트리와 $x$ 쪽 서브트리 둘 중 하나에 모두 몰려 있으므로 당연히 색칠하는 데 문제가 없을 것이고, $S_{odd}$의 경우 양쪽 서브트리에 하나씩 정점이 놓여 있을 것이기 때문에 기우성이 반전되어 문제가 없게 된다.

 

결론적으로, 우리는 위 두 조건을 만족하는 간선의 개수를 찾으면 되고, 이것은 Tree DP 등을 이용해 $O(N+M)$에 쉽게 처리할 수 있다.

$k=2$

우리는 앞서 $k=1$인 경우의 문제를 풀면서 값진 아이디어를 얻었다. 그것은 바로 bipartite coloring이다. 이 아이디어를 이용해 $k=2$인 경우도 해결할 수 있는지 살펴보자.

 

$k=2$인 경우, 두 개의 간선이 $T$에 속하는지 $S$에 속하는지에 따라 케이스를 조금 나눌 필요가 있다. 먼저 가장 쉬운 케이스부터 보자.

두 간선이 모두 $S$에 속하는 경우

일단 $k=2$인 경우를 고려하고 있으므로 $\left| S_{odd} \right| \ge 2$라는 사실을 알 수 있다. 그런데 $S_{even}$에 있는 간선을 제거하는 것은 여기서 아무런 도움을 주지 않는다. 따라서 $S_{odd}$의 간선 두 개를 제거하는 경우만 보면 된다. 그런데 두 간선 다 $S_{odd}$에 속하는 경우라면, $\left| S_{odd} \right| = 2$인 경우에만 가능함을 위와 같은 논리로 쉽게 알 수 있다.

 

결론적으로 $\left| S_{odd} \right| = 2$이면 $1$가지 경우가 가능하고, 아니라면 불가능하다.

한 간선은 $T$에 속하고, 한 간선은 $S$에 속하는 경우

먼저 $S$에 속한 간선을 제거한 상태의 그래프를 보자. 이 그래프는 $k_{min} = 1$일 것이고, 반대로 말하면 $k=1$일 때의 두 가지 조건을 존재하는 트리 간선이 존재한다는 뜻이다. 그 여부를 모든 back edge에 대해서 판단해 줄 수 있다면 문제를 쉽게 풀 수 있다.

 

어떤 back edge $(u, v)$에 대해, 해당 edge를 제거한 그래프에서 $T$에 속한 간선 $(p, x)$ (당연히 $p$가 부모다)을 제거했을 때 그래프가 이분 그래프가 될 조건을 다음과 같이 나타낼 수 있다.

• $(p, x)$는 $S_{odd} - (u, v)$에 속한 모든 edge $(a, b)$에 대해, $a$와 $b$의 경로 위에 있어야 한다.
• $(p, x)$는 $S_{even} - (u, v)$에 속한 모든 edge $(a, b)$에 대해, $a$와 $b$의 경로 위에 있지 않아야 한다.

두 조건을 모두 만족하는 간선의 수를 찾는 것은 . 자세히는, 다음과 같이 해결할 수 있다. 편의상 어떤 $S$ 내의 간선 $(u, v)$에 대해, $T$ 내의 간선 $(p, x)$가 $u$와 $v$의 트리 위의 경로에 속할 때, $(p, x)$가 $(u, v)$의 범위 안에 있다고 하자.

먼저 $S_{odd}$에 속하는 간선을 골랐을 경우를 생각해 보자. 다음 조건을 만족하는 간선의 목록 $P$를 전처리한다.

• $(p, x)$는 $S_{odd}$에 속한 edge $(a, b)$ 중 정확히 하나를 제외하고 모두에 대해, $a$와 $b$의 경로 위에 있어야 한다.
• $(p, x)$는 $S_{even}$에 속한 모든 edge $(a, b)$에 대해, $a$와 $b$의 경로 위에 있지 않아야 한다.

그 다음으로 $S_{odd}$에 있는 모든 edge $(u, v)$에 대해, $(u, v)$의 범위 안에 있지 않은 $P$의 간선의 개수를 세면 된다. 해당 간선은 $S_{odd}$에서 $(u, v)$를 제외한 모든 간선의 범위 안에 있고, $S_{even}$의 모든 간선의 범위 안에 있지 않다.

 

다음으로 $S_{even}$에 속하는 간선을 골랐을 경우를 생각해 보자. 이 경우에는 대칭적으로 조건을 바꿔 주면 똑같이 문제를 해결할 수 있다.

 

모든 과정은 적당한 트리 DP와 DFS를 통해 $O(N+M)$에 처리할 수 있다. 사실 $S_{odd}$별로, $S_{even}$별로 답을 구해야 하는 게 아니라 합만 구하면 되는 거라고 생각하면 구현이 훨씬 쉬워진다.

두 간선이 모두 $T$에 속한 경우

DFS spanning tree에서 두 간선을 잡았을 때, 그 위치 관계를 두 가지로 구분할 수 있다. 한쪽 간선이 다른쪽 간선의 조상에 해당되는 경우가 있고 (이것은 한 간선 $(a, b)$가 다른 간선 $(c, d)$와 비교했을 때 $a$와 $b$가 둘 다 $c$와 $d$의 조상임을 의미한다.) 그렇지 않은 경우가 있다. 각각의 경우로 나눠서 살펴보는 것이 유리하겠지만, 일단은 전체적인 풀이의 방향성을 먼저 떠올려 보자.

 

$T$의 두 간선을 지우는 것은 트리를 세 조각으로 쪼개지게 한다. 각각의 조각을 $A$, $B$, $C$라고 하고, 편의상 우리가 제거한 두 간선은 각각 $A$와 $B$, $B$와 $C$를 연결하는 간선들이라고 생각해 보자. 우리가 만약 두 간선을 잘 골라서 전체 그래프가 이분 그래프가 되었다고 한다면, 다음 성질이 만족해야 한다.

• $S$의 간선의 양끝점이 속한 집합이 $(A, A)$, $(B, B)$, $(C, C)$, $(A, C)$라면, 해당 간선은 $S_{even}$에 속해야 한다.
• $S$의 간선의 양끝점이 속한 집합이 $(A, B)$, $(B, C)$라면, 해당 간선은 $S_{odd}$에 속해야 한다.

이후의 풀이는 상당히 신경써줄 점이 많기 때문에 설명의 양이 많다.

두 간선이 서로 조상 관계가 아닌 경우

이 경우 양끝점이 $(A, C)$인 back edge가 존재하지 않기 때문에 무시하고 생각해도 된다. 제거할 두 tree edge의 LCA 정점 $x$를 고정하고, $x$에서 내려가는 각 방향의 서브트리에서 안전하게 제거 가능한 간선의 개수를 구한 뒤 두 개를 고르는 방법의 수를 찾아주면 된다.

 

먼저 우리가 제거할 두 간선은 $S_{even}$의 범위에 속하지 않아야 한다. 이것을 미리 전처리해 두면, 남은 간선들 중 두 개를 선택해 모든 $S_{odd}$에 간선이 하나씩 포함되게끔 하는 경우의 수를 찾으면 된다. 일단 두 제거할 간선의 LCA를 골라 $z$라고 하자. $z$라는 LCA가 가능하기 위해서는, $z$ 위쪽에서 끝나는 $S_{odd}$의 간선이 없어야 한다. 즉, 모든 $S_{odd}$의 간선은 $z$의 자식들 중 하나를 범위에 포함하고 있어야 한다. 그런데 생각해 보면, 여기서 고려해야 할 $z$의 후보가 그리 많지 않음을 알 수 있다. 어쨌든 두 간선을 서로 조상 관계가 아니도록 할 것이기 때문에, 고려해야 할 $z$의 집합은 $S_{odd}$의 모든 간선에서 깊이가 더 깊은 정점들의 LCA라는 것을 알 수 있다.

 

따라서, 해당 방식으로 먼저 $z$를 잡고, $z$가 아래쪽 끝점인 $S_{odd}$의 edge가 있는지 판별한다. (이런 것이 있으면 불가능이다) 그런 것이 없다면, 모든 edge의 위쪽 끝점을 $z$의 자손으로 생각해도 문제가 없다. 또한 아래쪽 끝점이 $z$의 최대 $2$개의 서브트리에 속하는지도 판별해야 한다. 사실 $z$의 조건상 하나의 서브트리에 속했다면 그쪽 방향의 자손이 $z$였을 테니 모순이고, 정확히 $2$개인지를 봐줘야 한다. ($3$개 이상이라면, 당연히도 두 간선으로 덮을 수가 없다.)

 

이제 해당 방향의 두 개의 서브트리에서 각각 $k=1$인 경우의 문제를 풀어 주면 된다. 각각의 서브트리에서 제거할 수 있는 간선의 수를 구한 뒤 곱해주면 이 경우를 해결할 수 있다.

두 간선이 서로 조상 관계인 경우

두 간선이 서로 조상 관계인 경우일 때는 생각하기가 조금 더 힘들다. 우리가 선택할 두 간선 중 위에 있는 것을 $e_1$, 아래쪽에 있는 것을 $e_2$라 하고, 각각의 양끝점을 $(x_1, p_1)$, $(x_2, p_2)$라고 하자. 우리는 $x_2$를 고정하고 생각해볼 것이다. 당연히 $p_2$도 자동결정된다.

 

이때, $S_{odd}$와 $S_{even}$ 각각에 대해 고려해야 할 위치관계는 다음 네 가지이다.

A	B	C	D
$e_2$를 포함하는 경우	$e_2$를 포함하지 않으나 그 조상 노드를 포함함	$e_2$와 루트의 경로와 공유하는 간선이 없고, $p_2$ 방향 서브트리에 존재	$x_2$의 서브트리에 존재

 

홀수 간선과 짝수 간선에 대해 위 A, B, C, D 케이스가 발생하는 경우, 각 간선을 OA-OD, EA-ED와 같은 식으로 표기할 것이다.

 

먼저 상대적으로 처리하기 쉬운 C와 D에 대해 살펴보자.

C와 D

OC와 OD는 존재하면 안 된다. 이런 경우 해당 $x_2$ 노드를 선택하는 것이 불가능하다. 따라서 OC와 OD의 존재 여부를 먼저 확인해야 한다. 이것은 트리 DP 전처리를 통해 가능하다.

 

EC와 ED는 존재해도 상관 없고, 해당 간선들은 자동으로 조건이 성립하므로 더 이상 고려하지 않아도 된다.

A

OA의 경우, $e_2$를 이미 포함하고 있기 때문에 $e_1$과 겹치지 않도록 해야 한다. OA 간선이 있다면, 모든 OA 간선 중 위쪽 끝점이 가장 깊이가 작은 것을 구해 두자. $e_1$은 최소한 이 정점 위쪽으로 잡아야 할 것이다.

 

EA의 경우, 반대로 생각해야 한다. $e_2$를 포함했으므로 $e_1$도 반드시 포함해야 한다. EA 간선이 있다면, 모든 EA 간선 중 위쪽 끝점의 깊이가 가장 큰 것을 구해 두자. $e_1$은 최소한 이 정점 아래쪽으로 잡아야 한다.

 

A 간선에 대한 정보는 위 두 정보를 얻어 두는 것으로 충분하다.

B

가장 어려운 케이스이다. $e_1$을 잡을 때, 모든 OB 간선의 교집합 안에 있게 하면서도 모든 EB 간선에 포함되지 않게 잡아야 한다.

 

먼저 OB 간선부터 생각해 보자. OB 간선의 경로와 $e_2$의 조상의 교집합 중 가장 깊이가 깊은 정점을 $t$라고 하자. 그림으로 나타내면 아래와 같다.

 

 

OB 간선에 대한 정보를 사전에 전처리해 준다면 정점 $t$에서 하는 것이 좋아 보인다. 물론 이 정점 $t$는 $e_2$를 어디로 잡느냐에 따라 달라지는 정보이긴 하다.

 

이제 정점 $t$ 입장에서 생각해 보자. 만약 어떤 OB 간선이 $t$의 조상 노드에서 시작해 $t$의 특정한 서브트리로 흘러 들어가는 경로를 가지고 있다면, $t$의 나머지 서브트리 입장에서는 이 OB 간선이 정점 $t$부터 시작되는 것과 같이 보일 것이다. 만약 $e_2$의 입장에서 정점 $t$를 공유하는 여러 OB 간선이 있다면, 그 중에서 위쪽 정점의 깊이가 가장 깊은 것을 알아내야 한다. (경로의 교집합을 찾는 것이므로…)

 

따라서 결론적으로 해야 할 것은 이렇다. 모든 $t$에 대해서, 해당 정점을 지나고, 해당 정점에서 더 올라가는 모든 $S_{odd}$ 간선들에 대해, 위쪽 끝점의 깊이가 가장 작은 것을 관리할 것이다. 값 하나만 저장하면 아래쪽 서브트리가 겹칠 수 있으니, 서브트리가 다른 후보를 최대 두 개까지 저장할 것이다. 이렇게 하고 나면, 실제로 $e_2$를 방문했을 때 $e_1$의 후보 구간을 찾는 것은 DFS에서 한 단계 내려갈 때마다 교집합을 처리하는 방식으로 해결할 수 있을 것이다.

 

이제 문제는 저 전처리를 어떻게 하는가에 대한 것이다. 저것 역시 또 다른 트리 DP를 통해 처리해줄 수 있다. Priority queue 두 개를 들고 큰작 트리 DP를 하면 $O(N \log^2 N)$에 처리할 수 있다. 전처리를 하는 방법을 알았으므로, 나머지 부분은 비교적 쉽게 해결할 수 있다.

 

다음으로 EB 간선을 처리하는 방법에 대해 생각해 보자. EB 간선에 대해서는 여집합의 교집합을 찾아야 하기 때문에 훨씬 더 어렵다. 그냥 교집합은 항상 연속된 구간을 이루지만, 여집합의 교집합은 그렇지 않기 때문이다. 이것을 처리하기 위해서는 먼저 OB와 비슷한 전처리를 할 것인데, 위쪽 끝점의 깊이가 가장 작은 지점들을 전처리해 줄 것이다. (이건 map을 쓰지 않고 그냥 단순 $O(N)$ 트리 DP에 하는 게 가능하다) 그리고 전처리한 값을 바탕으로 DFS를 할 때에는 단순히 교집합으로 처리를 하는 것이 아니라, 화성 지도 세그를 이용해서 불가능한 깊이들을 덮어 주는 식으로 업데이트와 쿼리를 처리하면 된다.

 

결과적으로, 문제를 총 $O(N \log^2 N)$에 해결할 수 있다.