이제는 플레를 향해 (#11375)

#11375 열혈강호 https://www.acmicpc.net/problem/11375

 

처음엔 열심히 풀었다.

 

틀린 코드

n, m = map(int, input().split())
people = {x: [] for x in range(1, n + 1)}
for i in range(1, n + 1):
    tmp = list(map(int, input().split()))
    if tmp[0]:
        people[i] = tmp[1:]

works = [0] * (m + 1)  # 인덱스 1부터 사용
# print(people)


def allocate(idx):
    # input()
    target = people[idx]
    if len(target):
        # 1. 가장 첫 번째 일에 연결
        for w in target:
            # hidden
            if works[w] == idx:
                continue
            # print(idx, w)
            if works[w] == 0:  # 2-1. 연결되지 않은 상태일 경우
                works[w] = idx  # 2-1-1. 현재 작업자를 연결
                return  # 2-2-2. 연결 성공 시 종료
            else:  # 2-2. 연결된 상태일 경우
                prev = works[w]
                allocate(prev)  # 2-2-1. 기존의 작업자를 이동
                if works[w]:  # 2-2-2. 기존 작업자의 이동이 불가한 경우
                    continue  # 2-2-2-1. 현재 작업자의 다음 일로, 2번부터 진행
                else:  # 2-2-3. 기존 작업자의 이동이 가능한 경우
                    works[w] = idx  # 2-2-3-1. 연결
                    return  # 2-2-3-2. 연결 성공 시 종료
        # 3. 이를 반복하고, 할당 가능한 일이 없는 경우, 포기. 현재 작업자를 버림.


for i in range(1, n + 1):
    allocate(i)
# print(people)
print(sum(map(lambda x: x > 0, works)))

 

논리적 사고 흐름을 그대로 옮겨 구현한 방식인데, 재귀 호출 횟수가 너무 많았다.

 

 

알고리즘 분류를 보니 "이분 매칭"이었다.

음... 이분 탐색도 아니고 이분 매칭이라니...

내가 모르는 알고리즘이 나오기 시작한다. 이게 플레티넘?

 

열심히 학습했다.

생각보다 단순해서 정말 놀랐다.

처음 이해하는 데 있어서 조금 버거웠지만,

이해해보니 DFS와 크게 다르지 않았다.

 

https://yjg-lab.tistory.com/209

[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)

 

 

정답코드

import sys

sys.setrecursionlimit(1000 * 1000)

input = sys.stdin.readline

n, m = map(int, input().split())
people = {x: [] for x in range(1, n + 1)}
for i in range(1, n + 1):
    tmp = list(map(int, input().split()))
    if tmp[0]:
        people[i] = tmp[1:]

visited = [False] * (m + 1)  # 인덱스 1부터 사용. 방문기록
workers = [0] * (m + 1)  # 인덱스 1부터 사용. 각 인덱스를 누가 처리하기로 했는지를 기록
# print(people)


def allocate(idx):
    for i in range(len(people[idx])):  # 가능한 일을 모두 순회
        now = people[idx][i]
        if visited[now]:  # 방문한 일이면 무시
            continue
        else:  # 방문하지 않은 일이면 진행
            visited[now] = True  # 방문처리
            if workers[now] == 0 or allocate(workers[now]):
                workers[now] = idx
                return True
    return False


for idx in range(1, n + 1):
    visited = [False] * (m + 1)
    if n == sum(map(lambda x: x > 0, workers)):
        print(n)
        exit()
    else:
        allocate(idx)
# print(people)
print(sum(map(lambda x: x > 0, workers)))

 

이제 이분 매칭 문제는 다 풀 수 있을 것 같다.