남자 m명과 여자 n명이 있다고 가정해 보겠습니다(m = n). 곧 파티가 열릴 예정이며, 각 남자는 반드시 여자 한 명과 함께 참석해야 합니다. 그래서 모든 남자가 여자들에게 초대장을 보내지만, 한 명의 여자는 오직 하나의 초대만 수락할 수 있습니다. 이때 우리가 구해야 할 것은 여자들이 실제로 수락할 수 있는 초대장의 총 개수입니다.
입력은 m x n 크기의 행렬로 주어집니다. 행렬의 각 위치 (i, j)는 남자 i가 여자 j에게 초대장을 보냈는지를 나타내며, 값이 1이면 초대장을 보낸 것이고 0이면 보내지 않은 것입니다.
예제
다음과 같은 입력이 주어졌다고 가정해 봅시다.
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
이 경우 출력은 3입니다.
- 여자 1이 남자 1의 초대를 수락합니다.
- 여자 2가 남자 3의 초대를 수락합니다.
- 여자 3이 남자 2의 초대를 수락합니다.
(여기서 인덱스는 1부터 시작합니다)
풀이 접근 방식
이 문제는 그래프 이론의 이분 매칭(Bipartite Matching) 문제와 동일합니다. 남자와 여자를 각각 두 그룹의 정점으로 보고, 초대 관계를 간선으로 연결하면 '최대 매칭(Maximum Matching)'을 찾는 것과 같습니다. 이를 위해 DFS(깊이 우선 탐색)를 활용한 증가 경로(Augmenting Path) 탐색 방법을 사용합니다.
해결 절차는 다음과 같습니다.
- dfs() 함수를 정의합니다. 이 함수는 node와 seen 두 매개변수를 받습니다.
- nei를 0부터 N-1까지 순회하면서 다음을 확인합니다.
- grid[node][nei]가 0이 아니고 seen[nei]가 False인 경우:
- seen[nei]를 True로 설정합니다.
- matching[nei]가 -1(아직 매칭되지 않음)이거나 dfs(matching[nei], seen)이 True를 반환하면:
- matching[nei]를 node로 설정하고 True를 반환합니다.
- grid[node][nei]가 0이 아니고 seen[nei]가 False인 경우:
- 모든 후보를 확인했는데도 매칭에 실패하면 False를 반환합니다.
- nei를 0부터 N-1까지 순회하면서 다음을 확인합니다.
- M은 grid의 행 개수, N은 grid의 열 개수로 설정합니다.
- matching 배열을 길이 N으로 생성하고 모든 값을 -1로 초기화합니다.
- 결괏값 res를 0으로 초기화합니다.
- i를 0부터 M-1까지 순회하면서 다음을 수행합니다.
- seen 배열을 길이 N으로 생성하고 모든 값을 False로 초기화합니다.
- dfs(i, seen)이 True를 반환하면 res를 1 증가시킵니다.
- 최종적으로 res를 반환합니다.
구현 예시
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(grid):
M, N = len(grid), len(grid[0])
matching = [-1] * N
def dfs(node, seen):
for nei in range(N):
if grid[node][nei] and not seen[nei]:
seen[nei] = True
if matching[nei] == -1 or dfs(matching[nei], seen):
matching[nei] = node
return True
return False
res = 0
for i in range(M):
seen = [False] * N
if dfs(i, seen):
res += 1
return res
print(solve([[1, 0, 0], [1, 0, 1], [1, 1, 0]]))
입력
[[1, 0, 0], [1, 0, 1], [1, 1, 0]]
출력
3
위 코드의 동작 원리를 살펴보면, 각 남자마다 DFS를 한 번씩 실행하여 아직 매칭되지 않은 여자를 직접 찾거나, 이미 매칭된 여자의 기존 파트너를 다른 여자에게 옮길 수 있는지 재귀적으로 확인합니다. 새로운 매칭이 성사될 때마다 결과값이 1씩 증가하며, 전체 시간 복잡도는 대략 O(M × E)(E는 간선, 즉 초대 관계의 개수) 수준으로 이 문제를 효율적으로 해결할 수 있습니다.