23086 두 반으로 나누기 (백준, python3)

 

시간 제한	메모리 제한
1초	1024MB

문제

종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다.

종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다.

종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 한다는 소문을 퍼뜨려 두 친구를 절교시키는 것이다! 친한 친구인 두 학생이 절교하면 더 이상 친한 친구가 아니게 된다.

종민이는 이런 식으로 절교시킬 친한 친구 쌍의 리스트를 만들었다. 물론 친한 친구 쌍들을 마구 절교시키다가 학생들끼리 파벌이 나뉘어 싸움이 나는 것은 원하지 않기 때문에, 해당 리스트의 모든 친한 친구 쌍을 절교시켜도 학생들끼리 파벌이 나뉘지는 않도록 했다. 파벌이 나뉘지 않는다는 말은, 친한 친구 관계인 두 학생을 모두 간선으로 이은 그래프가 연결 그래프임을 뜻한다.

종민이는 리스트에 쓰인 차례대로 친한 친구인 두 학생을 절교시킨 다음, 두 분반에 모두 친한 친구인 두 학생이 없도록 학생들을 배치하여 평화를 찾으려고 한다. 하지만 선생으로서 마지막 양심이 남아있었던 종민이는, 친한 친구 쌍을 절교시키는 일을 최소한으로 하려고 한다. 최소 몇 쌍의 친한 친구를 절교 시켜야 각 분반에 친한 친구인 두 학생이 없도록 학생들을 나눌 수 있을까?

 

입력

첫째 줄에 N, M, K가 공백으로 구분되어 주어진다.
- N은 5학년 3반의 학생 수이다.
- M은 5학년 3반의 친한 친구 쌍의 수이다.
- K는 종민이가 절교시킬 리스트에 포함되어 있는 친한 친구 쌍의 개수이다.

둘째 줄부터 M개의 줄에 걸쳐, i번째 친한 친구 쌍을 나타내는 ui, vi가 공백으로 구분되어 주어진다. 이는 ui번 학생과 vi번 학생이 친한 친구임을 뜻한다. 중복된 관계는 주어지지 않는다. 
M+2번째 줄부터 K개의 줄에 걸쳐 Ri가 주어진다. 이는 i번째로 절교시킬 친한 친구 쌍이 Ri번째 친한 친구 쌍임을 뜻한다. 입력되는 Ri는 모두 서로 다름이 보장된다.

 

출력

첫째 줄에 절교시켜야하는 최소 친한 친구 쌍의 개수를 출력한다.
둘째 줄에 두 분반의 각 학생 수를 오름차순으로 출력한다.
만약 리스트의 모든 친한 친구 쌍을 절교시켜도 두 분반으로 나눌 수 없다면, 대신 첫째 줄에 "-1"을 출력한다.

 

---

풀이

두 개의 반으로 나누었을 때 각 반에 친한 친구로 직접 연결된 학생이 없다는 조건을 잘 살펴보면 친한 친구 그래프 상에서 직접 연결된 정점들을 완전히 두 집합으로 분리할 수 있다는 것이고 그때 친한 친구 그래프는 이분 그래프가 된다.

 

절교 리스트를 순차적으로 끊어가며 이분 그래프 여부를 확인하게 되면 불필요한 연산을 굉장히 많이 반복하게 된다. 절교 리스트의 1번 친구 사이를 끊었을 때 그래프의 상태와 2번 친구 사이까지를 끊었을 때 그래프의 상태는 다르며 이전 상태의 결과를 다음 상태에서 활용할 수 없다. 따라서 k번 친구 사이까지를 끊었을 때 그래프의 상태를 확인하는 과정을 최소한으로 줄여야 한다.

 

k번째 친한 친구 쌍까지 절교시켰을 때, 이분 그래프가 형성된다면 좀 더 적은 수의 친구 쌍을 절교시켜도 이분 그래프가 만들어질 가능성이 있다. 반대로 이분 그래프가 형성되지 않는다면 좀 더 많은 수의 친구 쌍을 절교시켜야 이분 그래프가 될 수 있다. k를 특정하는 방법으로 이분 탐색을 활용할 수 있다. (이분 그래프에 이분 탐색이라니)

 

절교 리스트의 처음 s와 끝 e을 포인터로 잡고 중간 지점을 m이라고 했을 때, 절교 리스트의 m번째 친한 친구 쌍의 연결을 무시하고 그래프를 탐색했을 때 이분 그래프가 가능하다면 e를 m으로, 불가능하다면 s를 m+1로 옮겨주며 탐색을 반복한다. 가장 마지막으로 탐색이 가능했던 m은 e에 남아있고 이게 최소한의 k이므로 이 값을 반환한다. 두 학급의 학생 수는 이분 그래프 여부를 확인하는 탐색 과정에서 얻을 수 있다.

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
def solution():
    N, M, K = map(int, input().split())
    friends = [[] for _ in range(N + 1)]
    disconnect = [dict() for _ in range(N + 1)]
    f_list = [0]
    for _ in range(M):
        u, v = map(int, input().split())
        friends[u].append(v)
        friends[v].append(u)
        disconnect[u][v] = K + 1
        disconnect[v][u] = K + 1
        f_list.append((u, v))
    for i in range(1, K + 1):
        u, v = f_list[int(input())]
        disconnect[u][v] = i
        disconnect[v][u] = i

    def is_bipartite(k):
        check = [0] * (N + 1)
        bfs = deque([1])
        check[1] = 1
        count = [1, 0]
        while bfs:
            now = bfs.popleft()
            for next in friends[now]:
                if disconnect[now][next] <= k: continue
                if check[next]:
                    if check[now] == check[next]:
                        return False
                else:
                    check[next] = -check[now]
                    count[1 if check[now] == 1 else 0] += 1
                    bfs.append(next)
        count.sort()
        return count

    s, e = 0, K
    while s < e:
        m = (s + e) // 2
        if is_bipartite(m):
            e = m
        else:
            s = m + 1
    if is_bipartite(s):
        print(s)
        print(*is_bipartite(s))
    else:
        print(-1)
solution()