BOJ 16661 - Bimatching (Python3)

상위 100문제에서 Platinum II를 없애려고 오늘 티어작을 좀 했다. 완전히 새로운 개념인 일반 그래프 매칭(의 매우 한정적인 사용법인 최대 매칭의 수)을 배운 다음에 매우 기초적인 응용 문제인, 그래도 Diamond II 정도 되는 문제를 두 개 풀고 나서 그 다음으로 많이 풀린 이 문제를 살펴보았다. 중간에 포기할까 하고 다른 거 잡아먹으러 갔다 돌아오는 시간까지 합치면 총 두 시간 정도 쓴 것 같다.

Ruby IV나 되는 문제다. ICPC의 2차 예선 격인 Northern Eurasia Finals에 출제된 문제인데, 보스격 문제... 같다. 왜 자신이 없냐면, 저 셋의 13문제 중 이 문제가 난이도가 가장 높지만 Ruby V가 세 문제나 있기 때문이다. 이 정도면 도대체 누구를 통과시키려고 이런 구성을 내놓은 건지 의도가 궁금해진다. 러시아나 동구권에 코딩 괴물들이 많다곤 하지만 아무리 그래도 대회 동안에 Ruby를...?

 

그럼 본격적으로 풀이에 돌입해 보자. 문제 본문은 귀찮아서 삽입하지 않는다. 내가 임의로 한 번역을 삽입하도록 하겠다. 한국어로 번역이 힘든 부분은 다소 의역이 들어갔다.

---

문제

19세기, 춤은 귀족들이 학교에서 배우는 가장 중요한 과목 중 하나였습니다. 무도회는 낭만적인 목적 혹은 사업적인 목적으로 새로운 사람들을 알게 되는 중요한, 경우에 따라서 유일한 기회였습니다. 그러나 그 시대에는 많은 신사들이 전쟁에서 죽었습니다. 이러한 이유로 무도회에서 춤을 추는 신사들의 부족은 다소 흔한 문제였습니다. 하지만 이 문제에 대한 우아한 해결책이 발견되었습니다. 어떤 춤들은 신사 한 명이 한 명의 숙녀가 아니라 두 명의 숙녀와 함께 할 수 있도록 변형되었습니다. 두 명을 위한 기존의 춤만 아니라, 세 사람을 위한 새로운 춤이 나타난 겁니다.

오늘날 춤의 재구성에 관심이 있는 단체들이 생겨나고 있으며, 여전히 신사의 수는 숙녀의 수보다 적다고 합니다. 그래서 숙녀 - 신사 - 숙녀 세 명을 위한 춤들 또한 연구되고 있습니다.

베티는 유명한 역사적 춤 단체의 리더입니다. 불행하게도, 그 단체의 일부 신사와 숙녀가 같은 숙녀 - 신사 - 숙녀의 쌍에서 함께 춤을 추고 싶어하지 않는다고 합니다. 사려 깊은 베티는 그러한 감정의 골을 전부 알아차리고 있습니다. 그녀에게 필요한 것은 춤을 추기 위해 선택할 수 있는 최대 숙녀 - 신사 - 숙녀 쌍 \(T\)를 찾는 방법입니다. 그녀는 그러한 쌍을 구성하는 방법을 알 필요가 없다고 합니다. 왜냐하면 "그리고 이제 숙녀 - 신사 - 숙녀 쌍을 만들어 주세요. 전 그게 가능하다는 것을 아니까요."라고 말하며 사람들을 헷갈리게 하는 것을 좋아하기 때문입니다. 베티가 최대 숙녀 - 신사 - 숙녀 쌍을 찾을 수 있도록 도와줍시다!

 

입력

입력 데이터의 첫 번째 줄은 테스트케이스의 수 \(t\)를 나타내는 정수입니다. \((1\le t\le 20)\)

매 테스트케이스의 첫 줄에 신사의 수와 숙녀의 수를 나타내는 두 정수 \(N, M\)이 공백으로 구분되어 입력됩니다. \((1\le N, M; N+M\le 150)\)

그다음 \(N\)줄에 걸쳐 \(i\)번째 줄에 \(0\)과 \(1\)로만 구성된 길이 \(M\)의 문자열이 입력됩니다. 그 중 \(j\)번째 문자는 \(j\)번째 숙녀가 \(i\)번째 신사와 함께 숙녀 - 신사 - 숙녀 쌍을 이룰 수 있는 경우에 \(1\)이고, 아닌 경우 \(0\)입니다.

모든 테스트케이스에 대하여 \(N+M\)의 합은 최대 \(150\)입니다.

 

예제 입력)

# 예제 입력 1
2
2 3
111
111
3 4
0110
1100
0011

# 예제 입력 2
1
3 6
001100
111111
001100

 

출력

각 테스트케이스의 최대 숙녀 - 신사 - 숙녀 쌍의 수를 한 줄에 하나씩 출력한다.

 

예제 출력)

# 예제 출력 1
1
2

# 예제 출력 2
2

 

---

내 코드

# Not provided #

 

코드를 공개하지 않는다. 17646번 문제의 코드를 블로그에 공개한 적이 있었는데, 주석까지 베낀 양심이 없는 사람을 그 후로 세 명 발견했다. 그 중 둘은 내 코드를 확인하기까지 했다. 이 정도 난이도가 되는 문제는 코드를 공개하는 의미가 없다고 본다. 최소한 풀이 방법만 확인 후 자기 손으로 구현할 줄은 알아야 한다고 생각한다. 무슨 자격이 있어야 이런 주제넘는 말을 할 수 있을지는 모르겠지만, 일단 치팅의 피해자라면 발언권은 있다고 본다.

 

우선 이 문제를 푸는 알고리즘을 소개한 koosaga님의 블로그 포스트를 레퍼런스로 달아 두겠다. 여기서 소개한 알고리즘과 한 가지 매우 중요한 관찰만 있으면 이 문제를 풀 수 있다. 문제는 이 두 가지가 모두 결코 쉽지 않다는 것이다.

신사가 단 한 명의 숙녀와만 짝지어질 수 있다면 이는 이분 그래프에서 최대 매칭을 찾는 문제가 되고, 이는 상대적으로 쉬운 난이도를 가지는 이분 매칭 문제가 된다. DFS를 사용하는 시간복잡도 \(\mathcal{O}(VE)\)인 알고리즘이 가장 쉽고, \(\mathcal{O}(E\sqrt{V})\)인 Hopcropt-Karp 알고리즘이 그 다음으로 잘 알려져 있다. 플로우 등을 이용하는 방법도 있다고 하는데, 자세하게는 모른다.

 

아무튼. 신사와 신사, 숙녀와 숙녀는 절대 짝지어질 수 없고 숙녀 - 신사 - 숙녀 쌍의 최대 갯수를 구해야 하므로 이건 이분 그래프에서의 매칭 문제가 된다. 문제는 이분 매칭 알고리즘을 사용할 수 없다는 것이다. 신사를 흰색 정점, 숙녀를 검은색 정점으로 할당한 이분 그래프에서 하나의 흰색 정점이 0개 혹은 두 개의 검은색 정점과, 하나의 검은색 정점이 0개 혹은 한 개의 검은색 정점과 매칭이 되어야 하므로 일대일 대응(처럼 보이는) 이분 매칭 문제가 아니게 된다.

잠깐만, 뭔가 익숙한 냄새가 난다. 이분 매칭 기초 문제 중에서는 한 사람이 최대 두 개의 일을 할 수 있고 각각의 일을 담당하는 사람이 한 명인, 그러니까 이번 문제와 굉장히 비슷한 열혈강호 2라는 문제가 존재한다. 이것대로 하면 금방 풀릴까? 이 문제의 풀이는 사람에 해당하는 정점을 두 개로 분할하는 것이다.

 

결론부터 말하자면 아니다. 최대 매칭의 수를 2로 나눈 값이 답이 될 것이라고 생각하지만 그럴 수가 없다. 예제는 불행히도 그런 잘못된 시도에 대해 전부 답을 내지만, 다음과 같은 입력이 들어 올 때는 어떨까?

# 반례 1
1
4 5
11000
10100
10010
10001

이 반례의 답은 1이다. 하지만 이렇게 되면 단순한 정점 분할을 통한 이분 매칭의 시도는 매칭의 수가 5라고 답을 하게 된다. 답을 이 매칭의 수를 2로 나눈 몫을 취하는 경우 당연하게도 틀리게 된다. 이 시도는 하나의 흰색 정점이 단 하나의 검은색 정점과 연결되어도 문제 없이 매칭이 된다고 판별하기 때문이다.

 

그렇다면 어떻게 해야 할까? 이분 그래프의 형태를 유지시키는 방법으로는 답을 얻기 힘들어 보인다... 그렇다면 이분 그래프의 형태를 포기하면 된다.

\(i\)번 신사를 두 정점 \(g_i, g_i'\)로 분할하고, \(g_i, g_i'\)를 잇는 간선도 새로 만든다. 그렇다면 이 신사가 숙녀 - 신사 - 숙녀 쌍을 만들지 못할 경우 내부에서 매칭이 될 것이다. 하지만 \(i\)번 신사가 \(x, y\)번 숙녀와 한 쌍을 이룰 수 있게 된다면? 그렇다면 \(g_i-l_x, g_i'-l_y\)로 두 개의 매칭을 만들 수 있게 된다! 만일 \(x\)번 숙녀와만 매칭이 될 수 있다면 여전히 이 \(i\)번 신사를 포함하는 매칭은 \(g_i-l_x\) 혹은 \(g_i'-l_x\)로 하나다.

그렇다면 답은 나왔다. 정점을 분할하고, 각 신사를 나타내는 두 개의 정점 내부에도 간선을 만든다. 대신 이렇게 되면 이분 그래프의 모양이 아니게 되므로, 일반 그래프에서 최대 매칭을 찾아야 한다. 이분 매칭도 상대적으로는 쉽다고 했지만 solved.ac 기준 Platinum의 대단히 높은 난이도를 가지고 있는데, 이를 일반화한 알고리즘은 분명히 더욱 어려울 것이다. 그리고 실제로 어렵다.

\(\mathcal{O}(V^2E)\)의 시간복잡도를 가지는 느리며 구현도 복잡하지만 모든 일반 매칭의 모태가 된 Edmond's Blossom 알고리즘이 있고, ho94949님이 작성한 상수가 작고 심지어 짧기까지 한 \(\mathcal{O}(V^3)\) 알고리즘도 존재한다. koosaga님의 블로그에 따르면 2017년에 가중치 있는 일반 매칭을 구하는 \(\mathcal{O}(E\sqrt{V}\log{\sum W})\) 시간복잡도의 알고리즘도 발표되었다고 한다. 

 

하지만 직접 숙녀 - 신사 - 숙녀 쌍을 구할 필요가 없다는 단서 조건과 간선의 가중치를 전혀 고려할 필요가 없다는 사실, 그리고 루프 같은 것이 존재하지 않는다는 사실이 이 문제를 푸는 데 더 쉬운 방법을 보장한다. 이는 무작위화가 살짝 첨가된 상수 작은 \(\mathcal{O}(V^3)\) 알고리즘으로, 다음과 같은 반대칭행렬 Tutte matrix를 사용한다.

\[a_{ij}=\left\{ \begin{matrix} x_{ij} & (i,j)\in E\wedge i<j \\ -x_{ji} & (i,j)\in E\wedge i>j \\ 0 & \text{otherwise} \end{matrix} \right.\]

이 행렬에 perfect matching이 존재한다면 \(\det A\ne 0\)이다. 또한 적당히 큰 소수 \(p\)를 잡고, 각 \(x_{ij}\)에 랜덤으로 \(0<x_{ij}<p\)가 성립하도록 아무 정수나 집어넣는다. 그리고 가우스 소거법을 통해서 \(A\)의 rank를 구하면, 이 값은 높은 확률로 최대 매칭의 크기의 두 배라고 한다.

한 번 시행할 때 \(\mathcal{O}(V^3)\)만큼의 시간을 소모하며, \(V\)가 이 문제에서는 최대 300으로 매우 작으니 같은 그래프에 대해서 여러 번 돌려 줘도 된다. 나는 \(\frac{\text{rank}}{2}\) 값으로 같은 것이 여섯 번 나올 때까지 돌린 다음 여섯 번째 나온다면 이 값이 최대 매칭의 크기라고 가정하는 무작위화 알고리즘을 적용했다. 이 6이라는 숫자에 큰 의미는 없다. 한 번 돌리면 틀릴 수 있을 것 같고 10번은 너무 많은 것 같아서 대충 여섯 번만 쓰자... 하는 생각으로 작성했다. 그럼에도 PyPy3 기준으로 2초의 시간제한을 가지는 문제에서 500ms 이하의 시간을 소모하니, 크게 비효율적인 방식은 아닐 것이다.

아무튼 이렇게 작성한 코드를 돌리면 어렵지 않게(?) 문제를 풀 수 있다.

 

이로서 16661번의 풀이를 마친다.