MCMF 연습 시리즈

BOJ 2316 - 도시 왕복하기 2 (정점 분할) 풀이
BOJ 11408 - 열혈강호 5 (최소 비용 최대 유량) 풀이
BOJ 3640 - 제독 (정점 분할 + 최소 비용 최대 유량) 풀이

요즘 네트워크 플로우를 열심히 공부 중이다. 그리고 네트워크 플로우에 대한 문제를 풀다 보니깐
선행 학습에 대해 위상 정렬(?)이 되는 문제 3개를 찾았다.
도시 왕복하기 2 (2316), 열혈 강호 5 (11408) -> 제독 (3640)
그래서 이 세 문제를 차례대로 풀이해보겠다.

BOJ 2316 - 도시 왕복하기 2 링크
(2022.09.05 기준 P3)
(치팅하면 속상해)

문제

N개의 도시가 P개의 양방향 길로 연결되어 있을 때, 1번 도시와 2번 도시를 제외한 도시들을 두 번 이상 방문하지 않음을 만족하며 최대한 1번과 2번을 오갈 수 있는 횟수

알고리즘

1번과 2번 사이 데이터가 얼마나 많이 흐를 수 있는지 확인하는 문제이므로 네트워크 플로우 알고리즘인 최대 유량을 사용해야 한다.
그리고 정점을 한번씩만 방문해야 한다는 조건을 위해 정점 분할이라는 약간의 테크닉을 써야 한다.

풀이

최대 유량 문제에 방문 체크를 해야 하는 문제이다.
난 처음엔 당연히 visited 배열을 이용해 방문 체크를 하여 코드를 제출했지만 WA
이유는 다음과 같다.

최대 유량에선 반대 간선으로 유량을 흘려보내는 작업을 하며 증가 경로를 찾아내는 과정이 있는데, 만약 visited 배열을 쓰게 되면 그 정점을 아예 막아버리게 되서 반대 간선으로 유량을 흘리지 못하게 된다. 그래서 visited 배열을 쓰지 말아야 한다.

그럼 어떻게 해야 할까?
바로 정점 분할이다.
하나의 정점을 두 개로 나누는 것인데, in과 out으로 나누고 그 사이 간선의 용량을 1로 설정하면
여러 정점에서 in으로 많은 유량이 흘러도 out으로 1 밖에 흐르지 않기 때문에 결국 그 정점을 한 번만 쓰게 되는 것이다.
이는 반대 방향으로도 유량을 흘릴 수 있기 때문에 최대 유량 알고리즘은 잘 돌아가게 된다.
(in과 out 사이에도 역방향 간선을 만들어야 함)
정점 분할은 어떻게 하냐면, 간단하다. 입력받은 정점 개수나 정점의 최대값을 N이라고 하면, N*2만큼 용량, 유량, 연결 배열을 선언해주고 in이나 out을 i + N으로 설정하면 된다.

그리고 1번과 2번 사이를 오갈 수 있는 횟수를 구하는 것인데, 길은 어차피 양방향이다.
그래서 1 -> 2나 2 -> 1이나 루트는 같으므로 시작 지점은 1로, 끝 지점은 2로 잡아서 최대 유량을 구해주면 된다.

주의사항

시작과 끝도 정점 분할했으면 무조건 시작 지점을 out으로 설정하자.
끝은 항상 in

코드

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

def solve():
    N, P = map(int, input().split())

    # 정점 분할
    # 상태가 들어오는 in 노드는 i, 상태를 내보내는 out 노드는 i + N
    # 그러므로 전체 필요한 정점 수는 N * 2
    length = N * 2
    flow = [[0] * length for _ in range(length)]
    capacity = [[0] * length for _ in range(length)]
    connect = [[] for _ in range(length)]
    # in과 out을 연결
    for i in range(N):
        connect[i].append(i + N)
        connect[i + N].append(i)
        capacity[i][i + N] = 1
    # 길의 양 정점을 in과 out을 잘 구분하여 연결
    for _ in range(P):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        # a -> b
        connect[a + N].append(b)
        connect[b].append(a + N)
        capacity[a + N][b] = 1
        # b -> a
        connect[b + N].append(a)
        connect[a].append(b + N)
        capacity[b + N][a] = 1

    # 시작은 1, 끝은 2 (양방향이므로 1 -> 2나 2 -> 1나 똑같으므로 1 -> 2로 가는 루트를 전부 세어준다.)
    # 시작이 out이므로 0 + N = N
    # 끝은 in이므로 1 그대로
    start = N; end = 1
    answer = 0
    while True: # 최대 유량 알고리즘 시작
        prev = [-1] * length
        queue = deque([start])
        while queue:
            here = queue.popleft()
            if here == end:
                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[end] == -1:
            break
        # 유량은 어차피 1
        here = end
        while here != start:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            here = prev[here]
        answer += 1
    print(answer)

solve()

여담

네트워크 플로우를 공부하고 이에 대한 문제를 풀다 보면 pypy3 조차 시간 초과가 자주 나더라. 그래서 하나 알게 된 것은 메인 함수를 선언하여 모든 변수를 전역이 아니라 지역 변수로 받아서 처리하게 되면 시간이 생각보다 많이 줄어든다.
이제 앞으로 좀 무겁다 싶으면 전부 메인 함수를 선언하여 써야겠다.

그리고 태그에 대해 많은 고민을 했다.
최대 유량, 최소 비용 최대 유량, 최대 유량 최소 컷.
이 세 개를 따로 해야 할까 말까 고민하다가 그냥 네트워크 플로우라는 태그 하나로 합치기로 했다.
그래야 뭔가 깔끔할 것 같아서.

(이분 매칭은 네트워크 플로우이긴 하지만, 네트워크 플로우 개념을 정확하게 몰라도 학습 가능한 알고리즘이기 때문에 그대로 두기로 했다.)