🖋️ 문제
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.
첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.
농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.
입력
첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.
출력
첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.
🤔 접근
이 문제를 통해서 이분매칭 알고리즘에 대해 다시 한 번 공부해볼 수 있었다. 이분 매칭 알고리즘은 내가 군대에서 불침번 근무표 자동생성 프로그램을 만들 때 한셀(VBA)로 구현했던 경험이 있다. 이분 매칭 알고리즘은 간단히 말해서, 두 개의 정점들의 집합이 있을 때, 한 집합의 정점에서 다른 정점의 집합으로 1대1 대응으로 중복되지 않도록 연결할 수 있는 최대 간선 수를 구하는 것이다.
군대에서 이 알고리즘을 공부하면서 왜 불침번 근무표를 사람이 짜면 다들 불만이 있을 수밖에 없는지 알게 되었다... (생각보다 복잡하다...)
- 두 집합 간의 관계 그래프 생성
- 시작 집합의 모든 정점에 대해 bimatch 함수를 호출하되, visited 리스트가 필요한 이유는 재귀함수를 도는 과정에서 저장되어 있는 간선을 따라 되돌아가서 다시 길을 탐색하는 과정이 있는데, 현재 할당되어 있는 길을 다시 탐색하게 되면 무한 루프에 빠지기 때문이다.
- DFS로 가능한 정점을 수정해나가는 것을 반복한다.
- 선택된 정점 개수를 세준다.
💻 내 코드
# 2188
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
# 왼쪽 정점수, 오른쪽 정점 수
n, m = map(int, input().split())
# 왼쪽 정점에서 연결 가능한 오른쪽 정점 번호들
graph = []
for i in range(n):
tmp = list(map(int, input().split()))
graph.append(tmp[1:])
# 선택된 정점 번호
selected = [-1] * (m + 1)
def bimatch(N):
print(N)
print(visited)
print(selected)
if visited[N]:
return False
visited[N] = True
for num in graph[N]:
if selected[num] == -1 or bimatch(selected[num]):
selected[num] = N
return True
return False
for i in range(n):
visited = [False] * (n)
bimatch(i)
result = 0
for i in range(1, m+1):
if selected[i] >= 0:
result += 1
print(result)
print(selected)👍 제출
