제주도에 놀러가고 싶은 내 마음을 코딩에 꾹꾹 담아 풀이해보겠다.

BOJ 9413 - 제주도 관광 링크
(2022.09.22 기준 P2)
(치팅하면 제주도 평생 못감)

문제

N개의 교차로와 M개의 도로가 있고 한 교차로는 한 번만 방문 가능하다고 하면
임의의 교차로 s에서 임의의 교차로 t로 이동하는 경로를, 교차로들을 최대한 포함하면서 두 개의 경로를 만든다고 하면, 두 경로에 포함되는 교차로의 수

알고리즘

포함하는 교차로의 수를 비용이라고 생각하고 MCMF를 돌려야 한다.
그리고 각 교차로는 한 번만 방문 가능하므로 정점 분할을 해야 한다.

풀이

일단 먼저 제독 풀이를 보고 오자. 정말 거의 똑같다.
그러므로 다른 점만 설명하겠다.

일단 비용은 교차로의 수라고 할 수 있다.
하지만 교차로의 수가 최대로 되야 하기 때문에, 비용을 마이너스로 두고 나중에 비용의 합을 구할 때 거기에 비용을 빼주면 된다.
마치, 최대 힙 마냥?

그리고 이 문제는 시작점과 도착점이 정해져 있지 않다.
경로는 교차로를 하나만 포함해도 된다고 문제에 적혀져 있기 때문에, 모든 교차로는 Source와 Sink와 연결되어 있고 언제든지 Sink로 빠질 수 있다고 생각하면 된다.
그리고 꼭 source에서 한 정점으로 연결할 때도 비용을 -1로 두어야 한다.

그리고 항상 역방향 간선의 비용은 반대로 잡아주자! 이 문제에선 역방향 간선의 비용은 1로 두면 된다.

코드

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

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

    # 각 정점은 한 번만 방문 가능하므로 정점 분할하여 분할된 정점끼리 용량을 1로 설정
    # start는 0, end는 N * 2 + 1
    # 전체 필요한 정점 수는 end + 1
    start = 0; end = N * 2 + 1; length = end + 1
    connect = [[] for _ in range(length)]
    capacity = [[0] * length for _ in range(length)]
    cost = [[0] * length for _ in range(length)]
    flow = [[0] * length for _ in range(length)]

    # 각 정점별로 정점 분할 및 start와 end로의 연결
    for i in range(1, N + 1):
        # 정점 분할
        connect[i].append(i + N)
        connect[i + N].append(i)
        capacity[i][i + N] = 1
        # start -> 정점
        connect[start].append(i)
        connect[i].append(start)
        capacity[start][i] = 1
        cost[start][i] = -1 # 교차로의 수를 비용으로 설정
        cost[i][start] = 1 # 최대 비용이므로 마이너스로 잡자.
        # 정점 -> end
        connect[i + N].append(end)
        connect[end].append(i + N)
        capacity[i + N][end] = 1

    # 간선
    for _ in range(M):
        A, B = map(int, input().split())
        connect[A + N].append(B)
        connect[B].append(A + N)
        capacity[A + N][B] = 1
        cost[A + N][B] = -1 # 간선도 마찬가지로 교차로를 하나 더 방문하는 것이므로 -1
        cost[B][A + N] = 1

    # 최대 유량
    answer = 0 # 교차로의 수(비용)를 저장
    for _ in range(2): # 두 경로이므로 두 번만 돌림
        # SPFA
        prev = [-1] * length
        distance = [inf] * length
        q = [False] * length # 큐에 원소가 있는지 판별
        queue = deque([start])
        distance[start] = 0
        q[start] = True
        while queue:
            here = queue.popleft()
            q[here] = False
            for there in connect[here]:
                if capacity[here][there] - flow[here][there] > 0 and distance[there] > distance[here] + cost[here][there]:
                    distance[there] = distance[here] + cost[here][there] # 거리 갱신
                    prev[there] = here # prev 갱신
                    if not q[there]: # 큐에 없다면 넣어준다.
                        queue.append(there)
                        q[there] = True

        # 두 경로가 만들어지지 않는 예외 케이스가 있다고 문제에 나와있지 않으므로
        '''
        if prev[end] == -1:
            break
        '''
        # 위와 같은 if문은 필요 없다.
        # 유량은 어차피 1
        here = end
        while here != start:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            answer -= cost[prev[here]][here] # 비용을 마이너스로 넣었으므로 빼줘야 한다.
            here = prev[here]
    print(answer)

for _ in range(int(input())):
    solve()

여담

풀었던 문제가 많아질수록 비슷한 문제가 많아지니깐 쉽게 풀리는 문제가 많아지는 것 같다.
내 노력의 결실..?