m명의 소년과 n명의 소녀가 있고 m =n이 있다고 가정합니다. 파티가 시작되고 각 소년은 소녀와 함께 그 파티에 가야 합니다. 따라서 소년은 모든 소녀를 초대하고 소녀는 하나의 초대만 수락할 수 있습니다. 우리는 소녀들이 수락할 수 있는 소년들의 총 초대 수를 찾아야 합니다. 입력은 m x n 행렬로 제공되며, 여기서 각 셀 위치 i, j는 소년 i가 소녀 j에게 편지를 보냈는지 여부를 나타냅니다. 셀이 1이면 초대장이 전송되었음을 의미하고 0이면 초대장이 전송되지 않았음을 의미합니다.
따라서 입력이 다음과 같으면
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
그러면 출력은 3이 됩니다.
−
인 경우 출력은 3이 됩니다.소녀 1이 소년 1의 초대를 수락합니다.
소녀 2가 소년 3의 초대를 수락합니다.
소녀 3이 소년 2의 초대를 수락합니다.
(여기서 인덱스는 1부터 시작)
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dfs() 함수를 정의합니다. 이것은 노드가 필요합니다. 본
- 0 ~ N 범위의 nei에 대해
- 그리드[노드][nei]가 0이 아니고 본[nei]가 False이면
- 본[nei] :=사실입니다
- matching[nei]가 -1과 같거나 dfs(matching[nei], see)가 True이면
- 매칭[nei] :=노드
- 참 반환
- 그리드[노드][nei]가 0이 아니고 본[nei]가 False이면
- 거짓을 반환
- 0 ~ N 범위의 nei에 대해
- M:=그리드의 행 수
- N :=그리드의 열 개수
- 일치:=값 -1을 포함하는 크기 N의 목록
- res :=0
- 0~M 범위의 i에 대해
- seen :=False 값을 포함하는 크기 N의 목록
- dfs(i, see)가 True이면
- 반환 결과
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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