[백준][Python] 2188 축사 배정

[백준][Python] 축사 배정

문제

문제

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.

첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.

입력

첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

---

접근

유량 그래프와 네트워크 유량(Network Flow)

유량 그래프는
기존의 그래프의 간선에 용량(capacity) 이라는 속성을 추가한 방향 그래프이다.
유량 그래프에 대한 설명 전에 관련 용어를 간략하게 정리하면 다음과 같다.

Source: 시작점
Sink: 도착점
Capacity: 용량 (간선에서 소화 가능한 최대 양 or 값)
Flow: 유량 (간선에서 용량을 점유하고 있는, 사용하고있는 양 or 값)
c(a, b): 정점 a 에서 b로, 소화 가능한 용량 값
f(a, b): 정점 a 에서 b로, 사용하고 있는(쓴) 유량 값

유량 그래프가 만족해야 할 세가지 속성은 다음과 같다.

1. 용량 제한
   f(a, b) $\leq$ c(a, b)

2. 유량 보존
   source ~ sink와 연결된 정점 x에 대해, x로 들어오는 유량의 합 = x에서 나가는 유량의 합
   $\Sigma$ f(source, x) = $\Sigma$ f(x, sink)

3. 유량 대칭
   간선 a -> b가 있고, a->b의 capacity가 5라면,
   b -> a라는 가상의 간선이 있고, 해당 간선의 capacity는 0이라고 가정한다.
   그래서, a->b로 양수의 유량을 보낸다는것은, b->a로 같은 크기의 음수의 유량을 보내는 것으로 가정한다.
   f(a, b) = -f(b, a)

네트워크 유량(network flow)이란,
Source(시작점) → Sink(도착점) 으로 동시에 보낼 수 있는, 데이터나 사물의 최대 양을 구하는 알고리즘이다.

이를 설명한 이유는 이제 설명할 이분 매칭 알고리즘이 특수한 상황의 유량 그래프에 적용할 수 있는 알고리즘이기 때문이다.

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

입출력 예시를 그래프로 그려보면 다음과 같다.

그래프의 모든 정점을 2개의 그룹으로 분리할 수 있고,
각 그룹 내에있는 정점간에는 간선이 존재하지 않는(인접하지 않은) 이분 그래프임을 확인할 수 있다.

또한 각 정점은 간선을 하나씩만 가질 수 있다.
이는 모든 경로의 용량이 1인 유량 그래프를 의미하며
이러한 이분 그래프에서, 모든 경로의 용량이 1이면서, 모든 경로의 방향이 한 그룹에서 다른 그룹으로만 향할 때
그래프의 최대 유량을 구하는 방법이 이분 매칭 알고리즘이다.

우리는 최대한 많은 소를 축사에 넣어야 하며, 이러한 그래프의 최대 유량을 구한다는 것은 결국 두 그룹(소, 축사) 사이에 연결 가능한 간선의 최대 갯수를 구하는 것과 같다.

풀이

1. 소 그룹의 배열 A와 축사 그룹의 배열 B를 선언하고 모두 -1로 초기화 한다.
   두 배열은 인덱스를 해당 그룹의 정점으로 하고, 값을 해당 정점과 연결과 상대 그룹의 정점으로 하는 배열이다.
   예를 들어, A[a] = b 인 경우, 소 그룹의 정점a와 축사 그룹의 정점b는 a->b 로 연결되어있다.

2. 소 그룹에서 축사 그룹으로 연결하기 때문에,
   배열 A를 순회하며 아직 연결된 정점이 존재하지 않은 정점인 경우(A[i] == -1) 방문 체크 배열을 초기화 한 뒤
   DFS로 축사 그룹과의 연결을 시도한다.

3. DFS는 다음과 같은 순서로 진행된다.
   a. 소 그룹의 정점 a_node를 방문했다는 표시를 한다.
   b. a_node와 인접한 축사 그룹의 정점 b_node를 순회한다.
   c. 아래와 같은 경우에 a_node와 b_node를 연결하고, True를 반환한다.

   • b_node와 연결된 정점이 없는 경우
   • b_node와 연결된 정점(a_node$'$)이 있지만,
     a_node$'$를 이번 DFS에서 아직 방문하지 않았으며,
     a_node$'$이 다른 축사 그룹의 정점과 연결 가능한 경우

   d. b_node를 전부 순회했음에도 연결을 할 수 없는 경우 False를 반환한다.

코드

def solution(M, adj):
    answer = 0
    A = [-1] * (N)
    B = [-1] * (M+1)
    for i in range(N):
        if A[i] == -1:
            visited = [False] * (N+1)
            if DFS(A, B, i, visited, adj):
                answer += 1
    return answer


def DFS(A, B, a_node, visited, adj):
    visited[a_node] = True
    for b_node in adj[a_node]:
        if B[b_node] == -1 or (not visited[B[b_node]] and DFS(A, B, B[b_node], visited, adj)):
            B[b_node] = a_node
            A[a_node] = b_node
            return True
    return False


if __name__ == '__main__':
    import sys
    N, M = map(int, sys.stdin.readline().split())
    adj = []
    for _ in range(N):
        adj.append(list(map(int, sys.stdin.readline().split()))[1:])
    ans = solution(M, adj)
    sys.stdout.write(str(ans))

참고

• https://velog.io/@kasterra/%EC%9C%A0%EB%9F%89-%EA%B7%B8%EB%9E%98%ED%94%84-%ED%8F%AC%EB%93%9C-%ED%92%80%EC%BB%A4%EC%8A%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://gseok.gitbooks.io/algorithm/content/b124-d2b8-c6cc-d06c-d50c-b85c-c6b0/d3ec-b4dc-d480-cee4-c2a828-ford-fulkerson-c560-b4dc-baac-b4dc-ce74-d50428-edmonds-karp.html
• https://blog.naver.com/kks227/220807541506