[Python] 2188 - 축사 배정 (플래티넘4)

1. 문제 설명

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

2188번: 축사 배정

이게 원래 플래4였나..? 문제는 기억나는데 등급이 이렇게 높았다는 게 당황스럽다.

 

---

2. 아이디어

최대 유량 문제를 풀 듯이 풀 수도 있지만 난 그냥 dfs를 사용해서 풀었었다.

솔직히 지금까지도 최대 유량 알고리즘은 유령 간선 개념을 이해했다는 확신이 안 생겨서 껄끄럽다.

 

dfs를 이용한 풀이는 제법 단순하다.

한 번에 최적의 경우를 탐색하기 보다는 일단 소를 차례로 배정할 수 있는 곳에 배정하다가

현재 축사가 비어있거나 현재 축사에 들어있는 소가 다른 곳으로 옮길 수 있는 곳이 있다면

기존의 소를 다른 축사로 옮겨버린다.

 

예를 들어, 테스트 케이스로 주어진 경우를 살펴보자.

첫 번째 소를 우선 2번 축사에 집어넣는다.

두 번째 소는 2번 축사에 넣으려고 보니 이미 1번 소가 들어가 있으므로, 2번 소를 다른 축사로 옮기는 게 아니라

1번 소에게 다른 축사로 가도 괜찮은지 다시 물어본다. 5번 축사도 괜찮다니까 옮기고 나면

현재 2번 축사에 2번 소가 있고, 5번 축사에 1번 소가 있게 된다.

3, 4, 5번 소에 대해서도 같은 작업을 반복 수행하면 최종적으로 축사 배정이 끝난다.

 

---

3. 코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(idx, visited, barn, caw):
    if visited[idx] == True:
        return 0
    visited[idx] = True

    for favor in caw[idx]:
        if barn[favor] == 0 or dfs(barn[favor], visited, barn, caw):
            barn[favor] = idx
            return True
    return False
    
def solution():
    n, m = map(int, input().split())
    caw = [[] for _ in range(n+1)]
    barn = [0]*(m+1)

    for i in range(1, n+1):
        caw[i] = list(map(int, input().split()))[1:]
    for i in range(1, n+1):
        visited = [False]*(n+1)
        dfs(i, visited, barn, caw)
    cnt = 0
    for i in barn:
        if i > 0:
            cnt += 1
    print(cnt)

solution()