이분 매칭(Bipartite Matching) 시간 단축 방법

이전에 이분 매칭(Bipartite Matching)에 대해 설명을 올린 적이 있다.

이분 매칭 (Bipartite Matching) :: http://www.crocus.co.kr/499

이 코드에서 조금의 변화를 통해 시간 복잡도를 꽤나 많이 줄여보는 글을 써보고자 한다.

우선 지난 글에서 올린 코드를 보자.

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 201
#define MAX_M 201
 
using namespace std;
  
int n, m;
bool adj[MAX_N][MAX_M];
vector<int> aMatch, bMatch;
vector<bool> visited;
 
bool dfs(int a)
{
    if (visited[a])
        return false;
 
    visited[a] = true;
 
    for (int b = 0; b < m; b++)
    {
        if (adj[a][b])
        {
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
int bipartiteMatch()
{
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
 
    int size = 0;
 
    for (int start = 0; start < n; start++)
    {
        visited = vector<bool>(n, false);
 
       if (dfs(start))
            size++;
    }
 
    return size;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

이번에는 새로 코딩을 한 이분 매칭에 대해 한번 보자.

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 1000001
 
using namespace std;
 
int n;
int adj[MAX_N][2];
int aMatch[MAX_N];
int bMatch[MAX_N];
int visit[MAX_N];
int visitCnt = 1;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int next = 0; next < 2; next++)
    {
        if (adj[a][next])
        {
            int b = adj[a][next];
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int size = 0;
 
    for (int start = 0; start < n; start++)
    {
        visitCnt++;        
        size += dfs(start);
    }
 
    return size;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

사실 바뀐게 별로 없다. 

aMatch부분과 bMatch 부분을 벡터로 써도 되고, 배열로 써도 되고 그건 이분 매칭 알고리즘을 쓰는 코더 마음이다.

하지만 visit가 bool에서 int로 바뀌었다.

'메모리가 더 많이 들어서 별로이지 않나요?'

사실이다. bool -> int로 가는순간 4배의 메모리가 더 든다.

하지만 바로 위의 코드에서 MAX_N처럼 N 범위가 큰 경우 시간 복잡도가 엄청나게 차이난다.

visitCnt라는 변수로 visit 배열을 초기화 하지 않고, visitCnt를 증가시켜 

그 값이 방문 한 값이라 생각하고 계속 비교해준다면 초기화 해 줄 필요가 없다.

4배의 메모리를 더 먹지만, MAX_N*n의 시간 복잡도를 줄여주는 효과를 볼 수 있다.

참고로 memset함수는 O(MAX_N)이다.

bool Type이라면 MAX_N만큼 밀어야하는데, 그걸 n번 반복해야한다.

만약 알고리즘을 해결하는 코더라면, 무엇을 선택하겠는가? Memory? Time?

나는 후자를 줄이는 것을 선택할 것 같다.

우리가 알고리즘을 배우는 이유는 메모리와 시간복잡도를 최적화 하기 위해 공부한다.

하지만, 메모리와 시간에 대해 어느곳에 가치를 더 주고싶냐면 메모리는 언제든지 늘릴 수 있다.

하지만, 시간이라는 것은 그 시간내에 해결되지 못하면 작업이 계속 밀리게되고 결국 할 수 있는게 없어진다.

4배의 메모리, MAX_N*n만큼의 시간 복잡도. 참 묘한 관계이지만 visitCnt라는 변수 하나로 문제 하나를 풀고 못푼다는 것이

최적화를 위해 알고리즘을 배우는 또다른 묘미가 아닐까 싶다.

이러한 경우를 통해 같은 코드에서 하나만 달라져도 정답, 오답이 갈리는 문제를 소개해 주고싶다.

[1733번] 등번호 :: https://www.acmicpc.net/problem/1733

이분 매칭 문제이다. MAX_N은 100만이다. 어떤 방식을 선택하겠는가?