헝가리안 알고리즘 ( Hungarian Algorithm )
헝가리안 알고리즘은 여러 작업을 여러 사람에게 배정할 때 , 전체 비용이 최소가 되도록 1대1 매칭을 찾는 알고리즘이다.
예를 들어 이런 상황이라고 가정한다.
| 사람 | 작업 A | 작업 B | 작업 C |
| 욱진 | 9 | 2 | 7 |
| 한영 | 6 | 4 | 3 |
| 지은 | 5 | 8 | 1 |
각 숫자는 그 사람이 그 작업을 할 때 드는 비용이다.
목표는 다음과 같다.
한 사람은 하나의 작업만 맡고 ,
하나의 작업도 한 사람에게만 배정하면서 ,
전체 비용이 가장 작아지게 만들기욱진 → 작업 B
한영 → 작업 A
지은 → 작업 C
처럼 배정할 수 있고 이때 전체 비용은
욱진 B = 2
한영 A = 6
지은 C = 1
총 비용 = 9
이런 식으로 계산한다.
헝가리안 알고리즘이 필요한 이유
사람과 작업 수가 적으면 모든 경우의 수를 직접 비교할 수 있다.
3명의 작업자와 3개의 작업이면 가능한 배정은 6가지이다.
하지만 10명의 작업자와 10개의 작업이라면? 경우의 수는 3,628,800 이다.
20명의 작업자와 20개의 작업이면 경우의 수가 2,432,902,008,176,640,000 으로 경우의 수가 너무 커진다.
그래서 모든 경우를 직접 확인하는 방식은 현실적으로 어렵다.
헝가리안 알고리즘은 이런 문제를 훨씬 효율적으로 풀기 위한 방법이다.
어떤 문제에 쓰이나?
헝가리안 알고리즘은 보통 할당 문제 ( Assignment Problem ) 에 사용된다.
대표적인 예시는 다음과 같다.
| 상황 | 의미 |
| 직원 ↔ 업무 | 업무 배정 비용 최소화 |
| 택시 ↔ 승객 | 이동 거리 최소화 |
| 학생 ↔ 프로젝트 | 선호도 기반 배정 |
| 로봇 ↔ 목표 지점 | 이동 비용 최소화 |
| 게임 AI ↔ 타겟 | 적 유닛이 목표를 효율적으로 나눠서 공격 |
| 추적 알고리즘 | 이전 프레임 객체와 현재 프레임 객체 매칭 |
게임 개발에서도 꽤 쓸 수 있다.
예를 들어 적 5마리가 있고 , 플레이어 주변 공격 위치가 5개 있다고 가정한다.
적 A → 위치 1
적 B → 위치 2
적 C → 위치 3
...
이렇게 배정할 때 , 전체 이동 거리가 가장 짧아지도록 정할 수 있다.
핵심 아이디어
헝가리안 알고리즘의 핵심은 이것이다.
비용 행렬에서 값을 조정해도 최적 배정 결과는 바뀌지 않는다는 성질을 이용한다.
어떤 행 전체에서 같은 값을 빼도 , 그 행에 속한 선택지들의 상대적인 차이는 유지된다.
욱진 : A 9, B 2, C 7
욱진의 비용이 이렇게 있다고 가정한다.
여기서 가장 작은 값은 2 이다.
각 값에서 2를 빼면 결과는 이렇다.
욱진 : A 7, B 0, C 5
욱진 입장에서 가장 유리한 작업은 여전히 B 이다.
즉 , 행이나 열에서 같은 값을 빼는 것은 비용 구조를 단순화할 뿐 , 최적 배정의 본질을 크게 바꾸지 않습니다.
기본 흐름
헝가리안 알고리즘은 다음 순서로 진행된다.
1. 비용 행렬을 만든다.
2. 각 행에서 최솟값을 뺀다.
3. 각 열에서 최솟값을 뺀다.
4. 0을 이용해서 가능한 1:1 배정을 찾는다.
5. 충분한 배정이 안 되면 행렬을 조정한다.
6. 모든 사람이 하나씩 배정될 때까지 반복한다.예제
| 사람 | 작업 A | 작업 B | 작업 C |
| 수근 | 9 | 2 | 7 |
| 호동 | 6 | 4 | 3 |
| 승기 | 5 | 8 | 1 |
목표는 총 비용 최소화이다.
1. 각 행에서 최솟값 빼기
각 사람별로 가장 작은 비용을 찾는다.
수근 행 최솟값: 2
호동 행 최솟값: 3
승기 행 최솟값: 1
각 행에서 그 값을 뺀다.
| 사람 | 작업 A | 작업 B | 작업 C |
| 수근 | 7 | 0 | 5 |
| 호동 | 3 | 1 | 0 |
| 승기 | 4 | 7 | 0 |
이제 각 행마다 최소 하나의 0 이 생겼다.
2. 각 열에서 최솟값 빼기
이번에는 각 작업별로 열의 최솟값을 찾는다.
열 별 최솟값은 이렇다.
작업 A 열 최솟값: 3
작업 B 열 최솟값: 0
작업 C 열 최솟값: 0
작업 A 열에서 3을 뺀다.
| 사람 | 작업 A | 작업 B | 작업 C |
| 수근 | 4 | 0 | 5 |
| 호동 | 0 | 1 | 0 |
| 승기 | 1 | 7 | 0 |
3. 0을 보고 배정하기
이제 0 이 있는 위치를 확인한다.
수근 → 작업 B 가능
호동 → 작업 A 가능 또는 작업 C 가능
승기 → 작업 C 가능
가능한 배정은 이렇다.
수근 → 작업 B
호동 → 작업 A
승기 → 작업 C
원래 비용으로 다시 계산한다.
수근 → 작업 B = 2
호동 → 작업 A = 6
승기 → 작업 C = 1
총 비용 = 9
이 배정이 최적의 배정이다.
0 을 찾는 이유
헝가리안 알고리즘에서 0 은 이런 의미를 가진다.
현재 조정된 행렬에서 상대적으로 가장 좋은 선택지
행에서 최솟값을 빼면 각 사람마다 최소 하나의 0 이 생긴다.
수근 입장에서 가장 싼 작업
호동 입장에서 가장 싼 작업
승기 입장에서 가장 싼 작업
이런 후보들이 0 으로 표시된다.
그 다음 열에서도 조정하면 , 전체적으로 더 균형 잡힌 후보들이 0 으로 남게 된다.
결국 알고리즘은 이 0 들 중에서 겹치지 않게 선택할 수 있는 조합을 찾는다.
핵심 수학 원리
알고리즘이 동작하는 이유는 두 가지 성질 때문이다.
- 상대적 순서 보존 : 행 / 열 전체에서 같은 값을 빼도 최적 할당은 변하지 않는다.
- 이분 매칭 ( Bipartite Matching ) : 0 인 위치는 "비용 없이 선택 가능한 후보" 의미를 갖는다.
복잡도
- 시간 복잡도 : O(N³)
- 공간 복잡도 : O(N²)
브루트포스 (N! 탐색) 에 비해 압도적으로 빠르다.
만약 0 만으로 배정이 안 되면?
항상 위의 예제처럼 쉽게 풀리지는 않는다.
| 사람 | 작업 A | 작업 B | 작업 C |
| 수근 | 0 | 0 | 5 |
| 호동 | 0 | 0 | 3 |
| 승기 | 4 | 7 | 2 |
위와 같이 0 이 이렇게 몰려 있을 수 있다.
수근과 호동은 A 와 B 에만 0 이 있고 , 승기는 0 이 없다.
이때 헝가리안 알고리즘은 행렬을 다시 조정해서 새로은 0 을 만들어낸다.
1. 모든 0을 최소 개수의 선으로 덮는다.
2. 선으로 덮이지 않은 값 중 최솟값을 찾는다.
3. 덮이지 않은 값에서는 그 최솟값을 뺀다.
4. 두 번 덮인 교차점에는 그 최솟값을 더한다.
5. 다시 0을 이용해 배정을 시도한다.
처음 보면 조금 복잡하지만 , 목적은 단순하다.
현재 부족한 0 을 더 만들어서 모든 행과 열에 대해 1대1 매칭이 가능하게 만드는 것이다.
정사각형 행렬이 아닐 때
헝가리안 알고리즘은 기본적으로 N x N 행렬 , 사람 수와 작업 수가 같은 경우를 기준으로 한다.
그렇지만 작업자가 3명이고 작업이 5 개일 수도 있다.
이 경우에는 가짜 작업자와 가짜 작업을 추가해서 정사각형으로 만든다.
작업자가 3명 , 작업이 5 개라면 가짜 작업자 2명을 추가해서 정사각형으로 만들어 연산한다.
게임 개발에서의 활용
- EnemyAI 타게팅 : 여러 적이 여러 플레이어 / 오브젝트를 겹치지 않게 타겟 지정
- 유닛 웨이포인트 배분 : N 개 유닛이 N 개 목적지를 이동하며 총 이동거리 최소화
- 매치메이킹 : 플레이어와 플레이어 간 스킬 / 핑 차이 최소화 배정
- 자원 할당 : 작업자 유닛들에게 건설과 수집 임무 효율적으로 분배
헝가리안 알고리즘의 단점
| 단점 | 설명 |
| 구현이 복잡하다 | 단순 정렬이나 가까운 대상 찾기보다 코드가 어렵다. |
| 1대1 매칭에 적합 | 한 작업에 여러 명을 배정하는 문제에는 바로 맞지 않는다. |
| 실시간 대규모 처리에는 부담된다 | 매 프레임 많은 유닛에 적용하면 비용이 커질 수 있다. |
| 조건이 복잡하면 변형이 필요하다 | 우선순위 , 금지 조건 , 그룹 배정 등이 있으면 추가 처리가 필요하다. |
정리
- 비용표를 만든다.
- 각 행과 열을 조정해서 0을 만든다.
- 0은 좋은 선택 후보를 의미한다.
- 0들 중 겹치지 않는 조합을 찾는다.
- 부족하면 표를 다시 조정해서 0을 더 만든다.
- 모든 대상이 하나씩 배정되면 끝난다.