백준 11375 <열혈강호 1> / 백준 11376 <열혈강호 2> Python

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

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

---

열혈강호 1 의 경우 단순한 이분매칭입니다.

https://dev-diary-0717.tistory.com/170

https://dev-diary-0717.tistory.com/171

두 문제와 상황과 입력만 다를 뿐 정확히 같은 문제이니 참고하시면 될 것 같습니다.

 

열혈강호 2 의 경우에는 한쪽이 담당할 수 있는 반대 노드가 n 개일 경우입니다.

해당 경우에는 하나의 노드를 할당받을 수 있는 노드에서 n 개의 노드를 할당받을 수 있는 노드 쪽으로 이분매칭을 실행하면 됩니다.

 

다만 담당할 수 있는 업무가 n 개이므로 케이스를 n 개로 나누어 각각 처리해주면 됩니다.

 

이 외에도 일반적으로 사람마다 이분매칭을 n 번 실행해도 같은 결과를 얻습니다.

---

import sys

input = sys.stdin.readline

# 이분매칭

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

    # 방문했으면 패스

    if visited[idx]:

        return False

    # 방문

    visited[idx] = True

    # 담당할 수 있는 일 순회하며 확인

    for node in hope_list[idx]:

        # 담당할 수 있거나 배치된 사람을 옮길 수 있다면

        if not connected[node] or bimatch(connected[node], visited, connected, hope_list):

            # 담당

            connected[node] = idx

            return True

   

    return False

   

def solution(N, M, hope_list):

    # 담당한 일 리스트

    connected = [0 for _ in range(M+1)]

    # 순회

    for i in range(1, N+1):

        # 방문 목록

        visited = [False for _ in range(N+1)]

        # 이분매칭

        bimatch(i, visited, connected, hope_list)

   

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

 

# 입력

N, M = map(int, input().strip().split())

hope_list = [[]] + [list(map(int, input().strip().split()))[1:] for _ in range(N)]

solution(N, M, hope_list)

 

 

============================================================================================

import sys

input = sys.stdin.readline

# 이분매칭

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

    # 방문했으면 패스

    if visited[idx]:

        return False

    # 방문

    visited[idx] = True

    # 담당할 수 있는 사람 순회하며 확인

    for node in hope_list[idx]:

        # 해당 사람이 담당할 수 있는 첫 번째 업무가 비었으면

        if not connected[node][0]:

            # 담당

            connected[node][0] = idx

            return True

        # 해당 사람이 담당할 수 있는 두 번째 업무가 비었으면

        elif not connected[node][1]:

            # 담당

            connected[node][1] = idx

            return True

        # 담당하고 있는 첫 번째 업무를 다른 사람에게 옮길 수 있다면

        elif bimatch(connected[node][0], visited, connected, hope_list):

            # 담당

            connected[node][0] = idx

            return True

        # 담당하고 있는 두 번째 업무를 다른 사람에게 옮길 수 있다면

        elif bimatch(connected[node][1], visited, connected, hope_list):

            # 담당

            connected[node][1] = idx

            return True

   

    return False

   

def solution(N, M, hope_list):

    # 담당한 일 리스트

    # 일 -> 사람으로 매칭

    # hope list 반대로 재구성

    reverse_hope_list = [[] for _ in range(M+1)]

    for idx in range(len(hope_list)):

        for idx_n in hope_list[idx]:

            reverse_hope_list[idx_n].append(idx)

       

    connected = [[0, 0] for _ in range(N+1)]

    # 순회

    for i in range(1, M+1):

        # 방문 목록

        visited = [False for _ in range(M+1)]

        # 이분매칭

        bimatch(i, visited, connected, reverse_hope_list)

   

    print(sum([2-c.count(0) for c in connected]))

# 입력

N, M = map(int, input().strip().split())

hope_list = [[]] + [list(map(int, input().strip().split()))[1:] for _ in range(N)]

solution(N, M, hope_list)