포스트

[ 백준 ] 11375 열혈강호 ( Python )

게시
By KimJinwoo 9 분읽는 시간

BOJ 11375

문제 분석

이 문제는 강호네 회사에서 직원들과 일들 간의 최적의 매칭을 찾는 문제입니다. 각 직원은 특정 일들만 할 수 있고, 목표는 최대한 많은 일을 처리하는 것입니다. 이 문제의 핵심은 직원과 일 사이의 관계를 이분 그래프(Bipartite Graph)로 모델링하는 것입니다. 이분 그래프란 모든 정점을 두 개의 그룹으로 나눌 수 있는 그래프를 말합니다. 여기서는 직원들을 한 그룹으로, 일들을 다른 그룹으로 나눌 수 있습니다. 그리고 각 직원이 할 수 있는 일들 사이에 간선을 연결하면 이분 그래프가 됩니다.

이분 그래프에서 최대 매칭을 찾는 것은 이분 매칭(Bipartite Matching) 문제로 잘 알려져 있습니다. 이 문제를 해결하기 위해서는 각 직원이 할 수 있는 일들 중에서 아직 매칭되지 않은 일을 찾아 매칭을 시도하는 과정을 반복해야 합니다. 만약 해당 일이 이미 다른 직원과 매칭되어 있다면, 그 직원을 다른 일로 매칭시키는 것을 재귀적으로 시도해 봐야 합니다. 이런 방식으로 모든 직원에 대해 매칭을 시도하면 최대 매칭을 찾을 수 있습니다.

문제 해결 아이디어

이 문제를 해결하기 위해 저는 다음과 같은 아이디어를 떠올렸습니다.

  1. 우선 각 직원이 할 수 있는 일들의 정보를 인접 리스트로 표현합니다. 이렇게 하면 각 직원에 대해 매칭을 시도할 때 할 수 있는 일들을 빠르게 탐색할 수 있습니다.

  2. 그다음 DFS를 이용하여 각 직원에 대해 매칭을 시도합니다. 직원이 할 수 있는 일들 중에서 아직 매칭되지 않은 일이 있다면 해당 일과 매칭을 시도합니다.

  3. 만약 해당 일이 이미 다른 직원과 매칭되어 있다면, 그 직원을 다른 일로 매칭시키는 것을 재귀적으로 시도합니다. 이는 augmenting path를 찾는 과정과 같습니다. augmenting path란 매칭에 포함되지 않은 간선과 매칭에 포함된 간선이 번갈아 나오는 경로를 말합니다. 이런 경로를 찾아 매칭을 변경하면 매칭의 크기를 1 증가시킬 수 있습니다.

  4. 모든 직원에 대해 위의 과정을 반복하면 최대 매칭을 찾을 수 있습니다.

이 아이디어는 백트래킹(Backtracking)의 일종으로 볼 수 있습니다. 매칭을 시도하다가 실패하면 이전 상태로 돌아가서 다른 가능성을 탐색하는 것이기 때문입니다. DFS를 사용하기 때문에 recursion을 이용한 간결한 구현이 가능합니다.

구현 과정

위의 아이디어를 바탕으로 문제를 구현해 보겠습니다.

  1. 먼저 입력을 받아 인접 리스트 adj를 생성합니다. adj[i]는 직원 i가 할 수 있는 일들의 목록을 나타냅니다.

  2. 일과 직원의 매칭 정보를 저장할 리스트 match를 생성합니다. match[j]는 일 j와 매칭된 직원의 번호를 나타냅니다. 초기에는 어떤 일도 매칭되지 않았으므로 모두 0으로 초기화합니다.

  3. dfs 함수를 구현합니다. 이 함수는 직원 employee에 대해 매칭을 시도하는 역할을 합니다.

    • 직원이 할 수 있는 각 일 work에 대해:
      • 해당 일을 아직 방문하지 않았다면 방문 체크를 하고,
      • 해당 일이 아직 매칭되지 않았거나, 해당 일과 매칭된 직원을 다른 일로 매칭시키는 것이 가능하다면 매칭을 업데이트하고 True를 반환합니다.
    • 모든 일에 대해 매칭을 시도했는데도 실패했다면 False를 반환합니다.

  4. 이제 모든 직원에 대해 dfs 함수를 호출하여 매칭을 시도합니다. 매칭에 성공할 때마다 카운트를 증가시킵니다.

  5. 최종적으로 카운트한 값을 출력합니다. 이것이 최대 매칭의 크기, 즉 최대로 처리할 수 있는 일의 개수입니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(NM)입니다. 여기서 N은 직원의 수, M은 일의 개수입니다. 각 직원에 대해 DFS를 수행하는데, 이때 각 간선을 최대 한 번씩만 방문합니다. 간선의 개수는 최대 NM개 있을 수 있으므로 전체 시간 복잡도는 O(N*M)이 됩니다.

코드 최적화

위의 코드는 재귀 호출을 사용하기 때문에 Python의 기본 재귀 깊이 제한에 걸릴 수 있습니다. 이를 해결하기 위해 sys.setrecursionlimit()을 사용하여 재귀 깊이 제한을 늘려주었습니다.

또한 입력의 크기가 크기 때문에 input() 대신 sys.stdin.readline()을 사용하여 입력 속도를 향상시켰습니다.

전체 코드 보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

def max_bipartite_matching(N, M, employees):
    adj = [[] for _ in range(N + 1)]
    for i in range(N):
        for work in employees[i]:
            adj[i + 1].append(work)

    match = [0] * (M + 1)

    def dfs(employee, visited):
        for work in adj[employee]:
            if not visited[work]:
                visited[work] = True
                if match[work] == 0 or dfs(match[work], visited):
                    match[work] = employee
                    return True
        return False

    result = 0
    for employee in range(1, N + 1):
        visited = [False] * (M + 1)
        if dfs(employee, visited):
            result += 1

    return result

N, M = map(int, input().split())
employees = [list(map(int, input().split()))[1:] for _ in range(N)]
print(max_bipartite_matching(N, M, employees))

마무리

이 문제는 이분 매칭 알고리즘을 이해하고 구현하는 능력을 테스트하는 문제였습니다. DFS를 사용하여 augmenting path를 찾는 것이 핵심 아이디어였습니다. 이분 매칭은 네트워크 플로우 알고리즘 중 하나로, 최대 유량 문제를 해결하는 데에도 사용될 수 있습니다. 이 문제를 통해 이분 매칭 알고리즘에 대한 이해도를 높일 수 있었고, 코딩 인터뷰나 대회에서 유사한 문제를 만났을 때 자신 있게 해결할 수 있을 것 같습니다.

문제 해결 과정을 자세히 설명해 드렸는데, 이해가 되셨는지 모르겠네요. 혹시 더 궁금한 점이나 추가 설명이 필요한 부분이 있다면 말씀해 주세요. 성실히 답변 드리겠습니다!

문제풀이, 알고리즘
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.