61. 그래프 분할(Graph Partitioning) - 연회장 나누기 알고리즘

1. 개요

그래프 분할(Graph Partitioning)이라는 유명한 문제라고 한다.

솔직히 어떤 면에서 이 문제가 그래프 분할이라는 개념에 속하는지 모르겠다.

먼저 문제는 하나의 집단 N명을 동등하게 N/2로 나누어, A와 B에 배치해야 한다. 

이 때, 각각의 집단 서로 서로 친분 관계를 유지하는데, 이 친분 관계를 최대한 존중하는 쪽으로 분할하는 방법이다.

글로 보면 조금 어려워 보이지만, 결국은 N을 모든 N/2로 분할한 집단을 다 조사해서 가장 효율적으로 뽑아내면 된다.

즉, 모든 부분집합으로 체크하는 전수조사다.

그렇기에 전체 알고리즘의 틀은 지금껏 작성한 알고리즘과 토대를 같이한다.

단, 특징적인 점이 있다.

여기서 부분집합을 나눌 때, 원래의 집합을 이용하는 것이 아닌 이진수 비트로 각각의 사람을 대응시켰다.

이게 무슨 말이냐면, 만약 6명의 사람을 A와 B로 동등하게 나눈다고 할 때, 

0 0 0 1 1 1 이란 비트와

0 1 0 1 0 1 이란 비트가 있다고 하면,

0 0 0 1 1 1 비트는 0번 1번 2번 사람은 A에, 3번 4번 5번 사람은 B에 배치한 것을 의미한다. 마찬가지로

0 1 0 1 0 1 비트는 0번 2번 4번 사람은 A에, 1번 3번 5번 사람은 B에 배치한 것을 의미한다.

이렇게 이진수 비트로 대응시킨 이유는 입력한 N에 따라서 빠르게 만들 수 있는 모든 이진수 비트를 뽑아내서,

조건에 맞게 0의 개수와 1의 개수가 동등한 비트만을 집어넣어 알고리즘을 수행한다.

즉, 모든 부분집합을 빠르게 나열하기 위해 각각의 사람을 비트라는 체계로 분할한 것이다.

2. 문제

한 기업에 N명의 프로그래머가 있다. 훌륭한 성과를 낸 프로그래머들을 위해서 기업의 CEO께서 연회를 열기로 결정했다. 

하지만 N명을 모두 수용할 수 있는 연회장이 없어서 어쩔 수 없이 N/2명이 수용가능한 연회장 A와 B를 빌렸다. 

각각의 연회장에 프로그래머들을 분할하려고 했는데, 알고보니 각각의 프로그래머들 관계에서 온도차를 발견했다.

연회도 마음에 맞는 사람과 즐겨야 좋은 법.

그래서 CEO께선 최대한 친한 사람과 연회를 즐길 수 있도록 고심했다.

하지만 모두를 만족시킬 수 없기에, 어쩔 수 없이 친한 관계이지만 다른 연회장을 사용해야 할지도 모른다. 

이런 경우를 바로 단절을 의미하는 Cut이라고 한다.

이 Cut이 최소가 되게끔, 하는 알고리즘을 작성하라.

3. 코드 및 출력

3-1) Partition()

3-2) Check_Friends()

3-3) Check_Half()

3-4) 출력

4. 정리

점점 재귀적인 방법 풀이에서 새로운 개념이 깃든다. 점점 최초의 틀에서 조건을 추가하는 방법들을 어떻게 하는지 알겠다.

물론 이 틀은 재귀 방식이기에 데이터가 커지면 거의 수행속도가 기하급수적으로 증가할 것이라고 생각한다. 아직 더 좋은

방법들에 대해 잘 모르기에 계속 공부해나가자. 또한, 이제 재귀 방식에 그래프 개념이 새로 연결되고 있다. 발전하고 있다.

이번에 내 주변의 기대들을 깨고 싶지 않다. 정말. 그리고 어제 전화는 너무 감사했다. 항상 힘들고 주저앉고 싶을 때마다

지탱해주는 이들이 있다. 나중에 다 내가 잡아준다. 안 무너지게.