개구리의 개발 블로그 개구리의 개발 블로그

백준 11375번 열혈강호 파이썬, 네트워크 플로우 출처 - https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 네트워크 플로우 연습하고 싶어서 푼 문제였지만 에드몬드 카프로 풀면 시간 초과가 나온다. 덕분에(?) 이분 매칭을 공부할 수 있었다. 네트워크 플로우에 대한 개념을 알고 있었기 때문에 약간의 힌트만 보고 풀 수 있었다. 1. 풀이 sink 노드와 source 노드 없이 직원과 일 노드만 그래프로 표현한다. match 배열을 통해 ..