1. 문제 설명
11378번: 열혈강호 4
첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는
www.acmicpc.net
내가 진짜 싫어하는 문제다.
내가 봤을 때, 문제 의도는 열혈강호 1,2는 최대유량으로 풀고 3,4는 호프크로프트 카프 알고리즘을 써야하는데
파이썬으로 시도하면1, 2를 최대유량으로 푸는 순간 막힌다. (3,4는 호프크로프트 카프로도 안 풀린다.)
이 쯤부터 파이썬의 속도 한계를 느껴서 슬슬 C++로 갈아타기 위해 공부하던 시점이었지 싶다.
+) 얼마 전에 Python3로 해결하고 코드를 공개해주신 분이 계시길래 읽어봤는데 진짜 감탄만 나왔다.
보통 Python으로 해결한 사람이 잘 없는 문제는 코드 공개도 잘 안 해주는데 알고리즘의 신이 아닐까..
2. 아이디어
[C++] 백준 11375번 - 열혈강호
📖 문제 📋 코드 #include #include #include using namespace std; int N, M, ans; bool visited[1001]; int bm[1001]; // Bipartite Matching vector > node(1001); bool DFS(int personNum) { if (visited[p..
cocoon1787.tistory.com
당시에 이 블로그를 참고하진 않았지만, 지금 다시 찾아보니 설명을 굉장히 잘 해놓으셨다.
여기서 참고하는 게 좋을 듯하다.
알고리즘 공부하면서 대부분 다 이해하고 넘어갔는데 호프크로프트 카프 알고리즘은 당췌 뭔 소린지 모르겠다.
훗날 이해가 되어 이 게시물을 수정할 수 있는 날이 오기를..
3. 코드
열혈강호
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
# 호프크로프트 카프 전용 bfs 함수 : 특정 그룹의 각 정점에 레벨 매김 (이 경우엔 A그룹)
def bfs():
queue = deque()
for node in range(1, n+1):
if aMatch[node] == 0: # 매칭이 되어있지 않다면 level 0 시작
level[node] = 0
queue.append(node)
else:
level[node] = INF
level[0] = INF
while queue: # group A의 각 정점에 0, 1, 2, 3, ...의 레벨을 매김
node = queue.popleft()
if level[node] < level[0]: # 아직 level 갱신이 안 됐을 때
for nxt_node in adj[node]: # 현재 접근 중인 노드의 간선 정보 접근
if level[bMatch[nxt_node]] == INF:
level[bMatch[nxt_node]] = level[node] + 1
queue.append(bMatch[nxt_node])
return level[0] != INF
# 호프크로프트 카프 전용 dfs 함수 : 새 매칭을 찾아내면 true
def dfs(now):
if now:
for node in adj[now]: # Agroup의 now번 째 노드와 연결된 Bgroup의 node중에 매칭이 안 되었거나,
if level[bMatch[node]] == level[now] + 1 and dfs(bMatch[node]): # node에 연결된 now'과 now 레벨 차가 1밖에 안 나거나,
aMatch[now] = node # node에 연결된 now'이 매칭되지 않았거나, level이 1 차이 나는 경우에
bMatch[node] = now
return 1
level[now] = INF
return 0
return 1
def solution():
cnt = 0
while bfs():
for idx in range(1, n+1):
if aMatch[idx] == 0:
cnt += dfs(idx)
print(cnt)
if __name__ == "__main__":
n, m = map(int, input().split())
adj = [[]] # adj[i][j] = Ai와 Bj가 이어져 있는가?
for idx in range(1, n+1):
adj.append(list(map(int, input().split()))[1:])
aMatch = [0 for _ in range(n+1)] # group B와 연결된 정점 정보
bMatch = [0 for _ in range(m+1)] # group A와 연결된 정점 정보
level = [INF for _ in range(n+1)] # group A의 각 정점의 level
solution()열혈강호 2
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
# 호프크로프트 카프 전용 bfs 함수 : 특정 그룹의 각 정점에 레벨 매김 (이 경우엔 A그룹)
def bfs():
queue = deque()
for node in range(1, n+1):
if len(aMatch[node]) < 2: # 매칭 개수가 2개가 아니면 level 0으로 시작
level[node] = 0
queue.append(node)
else:
level[node] = INF
level[0] = INF
while queue: # group A의 각 정점에 0, 1, 2, 3, ...의 레벨을 매김
node = queue.popleft()
if level[node] < level[0]: # 아직 level 갱신이 안 됐을 때
for nxt_node in adj[node]: # 현재 접근 중인 노드의 간선 정보 접근
if level[bMatch[nxt_node]] == INF:
level[bMatch[nxt_node]] = level[node] + 1
queue.append(bMatch[nxt_node])
return level[0] != INF
# 호프크로프트 카프 전용 dfs 함수 : 새 매칭을 찾아내면 true
def dfs(now):
if now:
for node in adj[now]: # Agroup의 now번 째 노드와 연결된 Bgroup의 node중에 매칭이 안 되었거나,
if level[bMatch[node]] == level[now] + 1 and dfs(bMatch[node]): # node에 연결된 now'과 now 레벨 차가 1밖에 안 나거나,
aMatch[now].append(node) # node에 연결된 now'이 매칭되지 않았거나, level이 1 차이 나는 경우에
bMatch[node] = now
return 1
level[now] = INF
return 0
return 1
def solution():
cnt = 0
while bfs():
for idx in range(1, n+1):
if len(aMatch[idx]) < 2: # 매칭 개수가 2개 안 넘으면
cnt += dfs(idx)
if len(aMatch[idx]) < 2:
cnt += dfs(idx)
print(cnt)
if __name__ == "__main__":
n, m = map(int, input().split())
adj = [[]] # adj[i][j] = Ai와 Bj가 이어져 있는가?
for idx in range(1, n+1):
adj.append(list(map(int, input().split()))[1:])
aMatch = [[] for _ in range(n+1)] # group B와 연결된 정점 정보
bMatch = [0 for _ in range(m+1)] # group A와 연결된 정점 정보
level = [INF for _ in range(n+1)] # group A의 각 정점의 level
solution()열혈강호 3
import sys
input = sys.stdin.readline
INF = int(1e9)
def dfs(now, visited):
if visited[now]:
return False
visited[now] = True
for _next in adj[now]:
if bMatch[_next] == 0 or dfs(bMatch[_next], visited):
bMatch[_next] = now
return True
return False
def solution():
global k
cnt = 0
for start in range(1, n+1):
visited = [False for _ in range(n+1)]
if dfs(start, visited):
cnt += 1
for start in range(1, n+1):
visited = [False for _ in range(n+1)]
if dfs(start, visited):
cnt += 1
k -= 1
if k == 0:
break
print(cnt)
if __name__ == "__main__":
n, m, k = map(int, input().split())
adj = [[]] # adj[i][j] = Ai와 Bj가 이어져 있는가?
for _ in range(1, n+1):
adj.append(list(map(int, input().split()))[1:])
bMatch = [0 for _ in range(m+1)] # group A와 연결된 정점 정보
solution()열혈강호 4
import sys
input = sys.stdin.readline
INF = int(1e9)
def dfs(now, visited):
if visited[now]:
return False
visited[now] = True
for _next in adj[now]:
if bMatch[_next] == 0 or dfs(bMatch[_next], visited):
bMatch[_next] = now
return True
return False
def solution():
global k
cnt = 0
for start in range(1, n+1):
visited = [False for _ in range(n+1)]
if dfs(start, visited):
cnt += 1
for start in range(1, n+1):
while k > 0:
visited = [False for _ in range(n+1)]
if dfs(start, visited):
cnt += 1
k -= 1
else:
break
print(cnt)
if __name__ == "__main__":
n, m, k = map(int, input().split())
adj = [[]] # adj[i][j] = Ai와 Bj가 이어져 있는가?
for _ in range(1, n+1):
adj.append(list(map(int, input().split()))[1:])
bMatch = [0 for _ in range(m+1)] # group A와 연결된 정점 정보
solution()