[백준/2188] 축사 배정 (Python)

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

2188번: 축사 배정

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:08:06

 

---

 

문제 설명

 

 

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

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

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

 

 

입력 및 출력

 

입력

 

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

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

 

출력

 

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

 

입력 예시

 

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

 

출력 예시

 

4

 

 

---

 

풀이

 

이분 매칭을 사용해야 하는 문제.

 

기본적으로 i번째 소가 방에 들어갈 수 있는지 확인하려면, 깊이 우선 탐색을 진행하도록 한다. (이 때 방문한 노드를 visited에 저장한다)

 

• 만약 현재 소(node)의 탐색 중 이미 방문한 소에 탐색을 시도(visited[node] == True)한다면, 이 소를 포함한 모든 경우의 수를 테스트한 경우이므로 False를 반환한다.
• 그렇지 않다면, 이 소의 탐색 여부를 표기하고 다음으로 진행한다(vistied[node] = True)
  • 이 소가 들어갈 수 있는 축사를 전부 탐색한다.
  • 만약 어떤 축사가 배정되어있지 않다면, 그 축사에 배정하고 True를 반환한다.
  • 배정되어 있다면, 그 소가 다른 축사에 배정할 수 있는지 여부를 다시 살펴보아야 한다. 즉 dfs로 그 소를 탐색하여, 다른 축사에 배정할 수 있을 지 여부를 탐색한다. 만약 배정이 가능하다면 그 축사에 배정하고 True를 반환한다.
  • 모든 순환이 끝났을 때 배정이 완료되지 않았다면 false를 반환한다.

 

이런 식으로 dfs를 각 소에 대해 진행하여, 만약 True가 반환된다면 그 소의 축사 배정이 완료된 것이므로 정답을 1 카운트하면 된다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
rooms = [-1]*(M+1)
cows = [list() for _ in range(N)]

for i in range(N) :
  _, *room = map(int, input().split())
  cows[i] = room

def dfs(node) :
  if visited[node] :
    return False
  visited[node] = True
  for room in cows[node] :
    if rooms[room] == -1 or dfs(rooms[room]) :
      rooms[room] = node
      return True
  return False

result = 0
for i in range(N) :
  visited = [False]*(N+1)
  if dfs(i) :
    result += 1
print(result)

풀이 완료!