오랜만..!
백준 다이아 4 찍는데 열중한다고 최근 블로그 글을 쓰지 못했다.
오늘 오전에 다이아 4 찍었으니 다시 블로그 글을 열심히 써보겠다!

BOJ 9169 - 나는 9999번 문제를 풀 수 있다 링크
(2022.11.15 기준 P2)
(치팅하면 너는 모든 문제를 풀 수 없다)

문제

민혁이가 9999번 문제를 풀 수 있다와 없다로 진행한 투표에서 N명의 투표 결과가 나왔다.
N명 사이의 친구 관계 M개가 주어진다면, 친구 사이에 투표한 결과가 서로 다른 관계의 수와 자신의 생각과 반대로 투표를 해야 하는 사람 수의 합이 최소가 되게 출력

알고리즘

최대 유량 최소 컷 문제다.
투표 결과에 따라 간선을 적당하게 잇고 친구 관계에 따라 간선을 이은 다음 유량을 구하자.

풀이

source에는 풀 수 있다라고 한 사람들을, sink에는 풀 수 없다라고 한 사람들을 연결시켜보자.
그리고 친구 관계을 서로 연결시키자.

우리는 풀 수 있다와 없다를 나눠야 한다. 즉, source 집합과 sink 집합으로 나눠야 한다.
만약 같은 의견인 친구 관계인 두 사람은 굳이 의견을 바꿀 필요가 없다. 중요한 것은 다른 의견인 친구 관계. 그 관계 중 하나는 의견을 바꿔서 친구와 같은 의견이 되게 할 수 있다.
예를 들어 보자. A라는 사람이 있고, A의 친구들이 풀 수 있다와 없다로 나뉘는 두 그룹 P, Q가 있다고 생각하자.
만약 A가 풀 수 있다라면 Q 전부와 의견이 다르므로 합은 Q의 크기만큼 증가한다. 만약 풀 수 없다라고 생각을 바꾸면 P 전부와 의견이 달라진다. 그리고 생각을 바꿨으므로 합은 P의 크기 + 1 만큼 증가한다. 결국은 둘 중 한 쪽과 끊어내서 하나의 집합에 속해야 하는 것이다. 이를 최소 컷으로 해결하는 것이다.
최소 컷은 결국 최대 유량과 같다.
그러므로 풀이의 첫 부분에서 설명한 것처럼 간선을 잇고 그 간선들의 용량은 전부 1. 그리고 유량을 흘려 최대 유량을 찾아내자.

추가 설명을 간단히 하자면, 두번째 케이스를 그래프 모델링을 하여 나타내면
이렇게 되고, 빨간 선이 쳐져 있는 두 간선을 끊으면 두 집합으로 나뉘고, 저 두 간선의 용량의 합은 최대 유량과 동일 및 최소 컷이 된다.

첫번째 케이스 같은 경우는 source - 1번 간선을 끊어내면 두 집합으로 나뉜다.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

def solve(N, M):
    source = 0; sink = N + 1; length = sink + 1
    connect = [[] for _ in range(length)]
    capacity = [[0] * length for _ in range(length)]
    flow = [[0] * length for _ in range(length)]

    # 풀 수 있다는 source와 연결, 없다는 sink와 연결
    opinion = [0] + list(map(int, input().split()))
    for i in range(1, N + 1):
        if opinion[i]:
            connect[source].append(i)
            connect[i].append(source)
            capacity[source][i] = 1
        else:
            connect[i].append(sink)
            connect[sink].append(i)
            capacity[i][sink] = 1

    # 친구 관계 연결
    for _ in range(M):
        A, B = map(int, input().split())
        connect[A].append(B)
        connect[B].append(A)
        capacity[A][B] = 1
        capacity[B][A] = 1

    answer = 0 # 최대 유량 (최소 컷)

    while True:
        prev = [-1] * length
        queue = deque([source])
        while queue:
            here = queue.popleft()
            if here == sink:
                break
            for there in connect[here]:
                if capacity[here][there] - flow[here][there] > 0 and prev[there] == -1:
                    prev[there] = here
                    queue.append(there)
        if prev[sink] == -1: # sink로 더이상 갈 수 없다면 break
            break
        # 흐를 수 있는 최대 유량 찾기
        f = inf
        here = sink
        while here != source:
            f = min(f, capacity[prev[here]][here] - flow[prev[here]][here])
            here = prev[here]
        # 찾은 유량 흘리기
        here = sink
        while here != source:
            flow[prev[here]][here] += f
            flow[here][prev[here]] -= f
            here = prev[here]
        answer += f

    print(answer)

while True:
    N, M = map(int, input().split())
    if not N:
        break
    solve(N, M)

여담

사실 최소 컷에 대해 정확하게 알지 못했다가 최근 최소 컷 문제를 풀면서 원리 및 개념을 톡톡히 익히게 되었다. 내 코딩 실력이 상승하는 것 같아 뿌듯.