[LeetCode] 1820. Maximum Number of Accepted Invitations (Medium)

이 문제를 풀기 위해서는 이분 그래프 최대 매칭(Bipartite Matching), 그중에서도 Kuhn Algorithm에 대해서 알아야 한다.

Kuhn Algorithm은 이분 그래프에서 매칭의 수를 하나씩 늘려 가는 알고리즘이다. 핵심은 단순히 "빈 자리를 찾는다"가 아니라, 이미 누군가 차지한 자리라도 기존 매칭을 다른 곳으로 옮길 수 있다면 전체 매칭 수를 늘릴 수 있다는 점이다.

이 문제에서 남학생과 여학생은 자연스럽게 두 그룹으로 나뉜다.

• 왼쪽 그룹: 남학생
• 오른쪽 그룹: 여학생
• grid[i][j] === 1: i번 남학생이 j번 여학생을 초대할 수 있음

따라서 문제는 "가능한 초대 관계들 중 서로 겹치지 않게 최대 몇 쌍을 만들 수 있는가?"로 바뀐다.

1. 접근 : 문제를 단순화 하기

문제에서는 m x n 크기의 grid가 주어진다.

grid[i][j]가 1이면 i번 boy가 j번 girl을 초대할 수 있고, 0이면 초대할 수 없다.

여기서 제한 조건이 하나씩 붙는다.

• 한 boy는 최대 한 명의 girl만 초대할 수 있다.
• 한 girl은 최대 한 명의 boy의 초대만 받을 수 있다.
• 최대로 성사될 수 있는 초대 수를 구해야 한다.

즉, 어떤 boy가 어떤 girl을 선택하면 그 boy와 girl은 더 이상 다른 매칭에 사용할 수 없다. 이것은 그래프 관점에서 보면 정확히 matching이다.

처음에는 단순하게 greedy로 풀 수 있을 것처럼 보인다. 예를 들어 각 boy마다 가능한 첫 girl을 바로 선택하면 될 것 같다.

하지만 greedy는 쉽게 깨진다.

grid = [
  [1, 1],
  [1, 0]
]

만약 0번 boy가 0번 girl을 먼저 선택하면 1번 boy는 더 이상 선택할 girl이 없다. 결과는 1개다.

하지만 0번 boy가 1번 girl을 선택하고, 1번 boy가 0번 girl을 선택하면 결과는 2개가 된다.

여기서 중요한 포인트는 "이미 매칭된 girl을 포기해야 하나?"가 아니라, "그 girl과 매칭되어 있던 boy를 다른 곳으로 옮길 수 있나?"를 봐야 한다는 점이다.

이 과정을 DFS로 수행하는 방식이 Kuhn Algorithm이다.

2. Kuhn Algorithm이란?

Kuhn Algorithm은 이분 그래프의 maximum matching을 구하는 대표적인 augmenting path 기반 알고리즘이다.

여기서 matching은 서로 겹치지 않는 간선들의 집합이다. 이 문제에서는 "성사된 초대 쌍"이라고 보면 된다.

augmenting path는 현재 매칭 상태에서 매칭 수를 1개 늘릴 수 있는 경로를 의미한다.

조금 더 쉽게 말하면 다음과 같다.

1. 아직 매칭을 시도하지 않은 boy에서 시작한다.
2. 이 boy가 초대할 수 있는 girl을 하나씩 본다.
3. girl이 비어 있으면 바로 매칭한다.
4. girl이 이미 다른 boy와 매칭되어 있다면, 그 기존 boy가 다른 girl로 이동할 수 있는지 DFS로 확인한다.
5. 이동할 수 있다면 기존 boy를 옮기고, 현재 boy를 이 girl과 매칭한다.

이렇게 하면 단순히 빈 자리만 찾는 것이 아니라, 기존 배치를 재조정하면서 전체 매칭 수를 늘릴 수 있다.

Kuhn Algorithm은 종종 Hungarian Algorithm이라는 이름으로도 설명된다. 다만 알고리즘 문맥에 따라 "Hungarian Algorithm"은 비용이 있는 assignment problem을 푸는 알고리즘을 가리키기도 한다. 이 문제에서 쓰는 방식은 DFS로 augmenting path를 찾는 Kuhn Algorithm이라고 부르는 편이 더 정확하다.

3. 핵심 아이디어

우리는 girl 기준으로 현재 매칭 상태를 관리한다.

const matchGirl = Array(n).fill(-1);

matchGirl[j]는 j번 girl이 현재 어떤 boy와 매칭되어 있는지를 의미한다.

• matchGirl[j] === -1: 아직 아무 boy와도 매칭되지 않음
• matchGirl[j] === i: j번 girl은 현재 i번 boy와 매칭됨

이제 각 boy에 대해 DFS를 한 번씩 시도한다.

for (let boy = 0; boy < m; boy++) {
  const seen = Array(n).fill(false);
  if (canInvite(boy, seen)) answer++;
}

여기서 seen은 DFS 한 번 동안 이미 확인한 girl을 표시한다.

왜 매번 새로 만들까?

각 boy가 매칭을 시도할 때는 새로운 augmenting path를 찾는 것이다. 이전 boy의 DFS에서 어떤 girl을 봤는지는 현재 boy의 탐색과 직접적인 관련이 없다. 그래서 outer loop에서 boy가 바뀔 때마다 seen도 새로 만든다.

반면 matchGirl은 전체 매칭 상태이므로 끝까지 유지한다.

4. 단계별로 구현하기

4-1. 현재 매칭 상태 만들기

먼저 boy 수와 girl 수를 구하고, girl 기준 매칭 배열을 만든다.

const m = grid.length;
const n = grid[0].length;
const matchGirl = Array(n).fill(-1);

이 문제의 제약은 m, n < 200이기 때문에 DFS 기반 Kuhn Algorithm으로 충분하다.

4-2. canInvite 함수 정의하기

canInvite(boy, seen)은 현재 boy가 새로운 매칭을 만들 수 있는지 확인한다.

const canInvite = (boy, seen) => {
  for (let girl = 0; girl < n; girl++) {
    if (grid[boy][girl] === 0 || seen[girl]) continue;

    seen[girl] = true;

    if (matchGirl[girl] === -1 || canInvite(matchGirl[girl], seen)) {
      matchGirl[girl] = boy;
      return true;
    }
  }

  return false;
};

여기서 가장 중요한 부분은 이 조건이다.

if (matchGirl[girl] === -1 || canInvite(matchGirl[girl], seen)) {
  matchGirl[girl] = boy;
  return true;
}

두 가지 경우에 현재 boy를 이 girl과 매칭할 수 있다.

1. matchGirl[girl] === -1
   • girl이 비어 있으므로 바로 매칭할 수 있다.
2. canInvite(matchGirl[girl], seen)이 true
   • 이 girl과 이미 매칭된 기존 boy가 다른 girl로 이동할 수 있다.
   • 그러면 이 girl을 현재 boy에게 넘겨도 전체 매칭이 유지된다.

이 두 번째 경우가 Kuhn Algorithm의 핵심이다.

4-3. 모든 boy에 대해 매칭 시도하기

이제 모든 boy를 시작점으로 삼아 DFS를 실행한다.

let answer = 0;

for (let boy = 0; boy < m; boy++) {
  const seen = Array(n).fill(false);
  if (canInvite(boy, seen)) {
    answer++;
  }
}

canInvite가 true를 반환했다는 것은 현재 boy를 포함해서 매칭 수를 1개 늘릴 수 있었다는 뜻이다.

따라서 answer를 1 증가시킨다.

5. 예제로 따라가기

예를 들어 다음과 같은 입력이 있다고 하자.

grid = [
  [1, 1, 1],
  [1, 0, 1],
  [0, 0, 1]
]

가능한 한 가지 최적 매칭은 다음과 같다.

• Boy 0 -> Girl 1
• Boy 1 -> Girl 0
• Boy 2 -> Girl 2

총 3개의 초대가 성사된다.

여기서 Boy 2는 Girl 2만 가능하다. 만약 앞에서 Girl 2를 다른 boy가 가져갔다면, DFS는 그 boy를 다른 girl로 옮길 수 있는지 확인한다. 옮길 수 있다면 Girl 2를 Boy 2에게 주고, 기존 boy는 다른 girl과 매칭한다.

이렇게 매칭을 "다시 배치"할 수 있기 때문에 greedy보다 강하다.

6. 엣지 케이스

다음 케이스들을 생각해볼 수 있다.

grid = [[0, 0, 0]]

초대할 수 있는 관계가 하나도 없으므로 답은 0이다.

grid = [[1], [1], [1]]

모든 boy가 같은 girl만 초대할 수 있다. girl은 한 명의 초대만 받을 수 있으므로 답은 1이다.

grid = [
  [1, 0],
  [1, 1]
]

처음에는 둘 다 Girl 0을 바라볼 수 있지만, Boy 1은 Girl 1로도 갈 수 있다. 따라서 최종적으로 2개 매칭이 가능하다.

이런 케이스에서 Kuhn Algorithm의 재배치 로직이 제대로 동작하는지 확인할 수 있다.

7. 최종 구현

결과적으로 최종 구현은 다음과 같다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maximumInvitations = function(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const matchGirl = Array(n).fill(-1);

  const canInvite = (boy, seen) => {
    for (let girl = 0; girl < n; girl++) {
      if (grid[boy][girl] === 0 || seen[girl]) continue;

      seen[girl] = true;

      if (matchGirl[girl] === -1 || canInvite(matchGirl[girl], seen)) {
        matchGirl[girl] = boy;
        return true;
      }
    }

    return false;
  };

  let answer = 0;

  for (let boy = 0; boy < m; boy++) {
    const seen = Array(n).fill(false);
    if (canInvite(boy, seen)) {
      answer++;
    }
  }

  return answer;
};

8. 시간복잡도

boy의 수를 B, girl의 수를 G, 가능한 초대 관계의 수를 E라고 하자.

Kuhn Algorithm은 각 boy에서 augmenting path를 찾기 위해 DFS를 수행한다.

• 시간복잡도: O(B * E)
• 이 문제의 matrix 기준 최악의 경우: E = B * G이므로 O(B^2 * G)
• 공간복잡도: O(G + B)

matchGirl과 seen은 girl 수만큼 필요하고, 재귀 DFS 깊이는 최대 boy 수 정도로 보면 된다.

이 문제는 B, G < 200이기 때문에 이 방식으로 충분히 통과 가능하다.

참고자료

• LeetCode: https://leetcode.com/problems/maximum-number-of-accepted-invitations/
• doocs/leetcode 1820 README: https://github.com/doocs/leetcode/tree/main/solution/1800-1899/1820.Maximum%20Number%20of%20Accepted%20Invitations
• Kuhn Algorithm: https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html

Step by step goes a long way.