백준 3295 <단방향 링크 네트워크> Python

https://www.acmicpc.net/problem/3295

---

해당 문제는 이분매칭으로 풀 수 있는 문제입니다.

이분매칭 문제는 보통 왜 이분매칭으로 풀 수 있는지 이해하는게 어렵습니다.

 

문제에서 보면 선형 배열은 K-1 의 가치를, 링은 K 의 가치를 갖습니다.

그런데 이 수치는 해당 배열과 링이 갖고있는 노드의 수와 같음을 알 수 있습니다.

결국 해당 문제는 '노드끼리 가장 많이 연결할 수 있는 경우를 찾아라' 를 요구하고 있습니다.

 

또 선형배열과 링은 하나의 노드 안에 들어가는 엣지와 나가는 엣지가 모두 하나 이하로 존재합니다. 즉 연결된 모든 노드는 1 대 1 매칭이 된다는 말입니다.

 

정리해보자면 '노드를 연결할 건데 모든 노드끼리는 1 대 1로 매칭이 되고 해당 조건 아래에서 가장 노드를 많이 연결할 수 있는 경우를 찾아라' 이고 이 문제는 결국 모든 엣지의 코스트가 1 이고 모든 노드를 나가는 노드와 들어가는 노드로 나눌 수 있는 네트워크 플로우 문제라는 사실을 알 수 있습니다. 즉 이분매칭 문제입니다. 

 

---

import sys

input = sys.stdin.readline

# 이분매칭

def bimatch(idx, connectable, connected, visited):

    # 이미 방문한 노드면 탐색 안함

    if visited[idx]:

        return False

    # 방문 체크

    visited[idx] = True

    # 탐색 가능한 노드 탐색

    for node in connectable[idx]:

        # 연결할 수 있거나 연결된 노드를 다른 노드로 옮길 수 있다면

        if connected[node] < 0 or bimatch(connected[node], connectable, connected, visited):

            # 연결

            connected[node] = idx

           

            return True

       

    return False

def solution(n, m, data_list):

    # 탐색 가능한 노드 정리

    connectable = [[] for _ in range(n)]

    for o, i in data_list:

        connectable[o].append(i)

    # 연결된 노드

    connected = [-1 for _ in range(n)]

    # 시작 노드 순회

    for idx in range(n):

        # 방문 목록

        visited = [False for _ in range(n)]

        # 이분 매칭

        bimatch(idx, connectable, connected, visited)

   

    print(sum([1 for c in connected if c >= 0]))

   

# 입력

T = int(input().strip())

for t in range(T):

    n, m = map(int, input().strip().split())

    data_list = [list(map(int, input().strip().split())) for _ in range(m)]

    solution(n, m, data_list)