visited 배열의 생성은 단 한번이면 충분하다. 또한 DFS 함수 내부에서 DFS 함수를 다시 재귀적으로 호출할 때에 visited 배열을 검사하게 된다. 만약 DFS 호출 시에도 매칭에 실패한다면, 그 노드를 검사했을 때 더 이상의 갱신이 불가능하다는 의미이다. 따라서 이 때는 visited[node]를 그대로 True로 둔다. 매칭이 성공한다면, 또 그 노드를 검사했을 때 갱신이 가능한지의 여부를 아직은 알 수 없으므로 visited[node]를 False로 다시 바꾼다.
풀이 코드
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
work_list = []
for _ in range(N):
n, *lst = map(int, input().split())
if not n:
N -= 1
else:
work_list.append(lst)
work = [-1] * (M + 1)
visited = [False] * N
ans = 0
def dfs(node):
for w in work_list[node]:
if work[w] == -1:
work[w] = node
return True
for w in work_list[node]:
if visited[work[w]]:
continue
visited[work[w]] = True
if dfs(work[w]) :
visited[work[w]] = False
work[w] = node
return True
return False
res_0, res_1 = 0, 0
for i in range(N):
if dfs(i):
res_0 += 1
if res_0 == M:
break
for i in range(N):
if len(work_list[i]) == 1:
continue
if dfs(i):
res_1 += 1
if res_0 + res_1 == M or res_1 == K:
break
print(res_0 + res_1)