USACO 2014 January Contest Gold 3번 - Ski Course Rating 풀이

 

(24.10.07 - AC 코드 전체를 추가하였습니다.)

 

 

https://www.acmicpc.net/problem/9877

 

백준 알고리즘 태그에는 병렬 이분 탐색도 함께 붙어있습니다만, 이 글에서는 단순 분리 집합(유니온 파인드) 풀이를 제시합니다.

 

문제에서는 그래프를 $M$개의 행, $N$개의 열로 표현하고 있습니다만, 여기서는 $N$개의 행, $M$개의 열을 가진 그래프로 바꿔 설명하겠습니다. 또, 맨 왼쪽 위를 $0$행 $0$열로, 맨 오른쪽 아래를 $N-1$행 $M-1$열로 나타내도록 하겠습니다.

이때 그래프의 $i$행 $j$열의 원소를 $i*M+j$번 노드라고 표현하면, 이 노드는 $i*M+j-1$번 노드(현재 노드의 왼쪽 노드), $i*M+j+1$번 노드(현재 노드의 오른쪽 노드), $(i-1)*M+j$번 노드(현재 노드의 위쪽 노드), $(i+1)*M+j$번 노드(현재 노드의 아래쪽 노드)와 인접해있음을 알 수 있습니다. 이 인접한 노드들을 잇는 간선의 가중치를 $w$라 하고, $w$를 양쪽 두 노드 값의 차로 정의합시다.

 

여기서 MST 구성 알고리즘 중 크루스칼 알고리즘처럼 간선들을 가중치의 오름차순으로 정렬한 뒤 유니온 파인드를 진행합니다. 어떤 두 노드 $u$, $v$를 잇는 간선의 가중치가 $w$라고 합시다. 이때 $u$와 $v$를 연결(유니온)함으로써 크기가 $sz$인 컴포넌트 Comp가 새롭게 생성되었다면, Comp에 들어있는 모든 노드들은 difficulty rating이 $w$인 상태에서 $sz$개의 노드들에 도달할 수 있음을 알 수 있습니다. 

 

따라서 어떤 두 노드 $u$, $v$를 잇는 간선으로 인해 어떤 컴포넌트의 크기가 $T$ 이상이 되었고, 그 컴포넌트에 들어있는 노드들의 difficulty rating이 처음으로 매겨진다면 그때의 그 difficulty rating은 $w$가 된다고 할 수 있습니다. 이러한 방법으로 모든 노드의 difficulty rating을 전처리할 수 있습니다.

 

 

 

<코드 분석>

구현 코드(cpp)

 

 

1. 간선 생성

//간선을 중복해서 만들지 않도록 dirx[], diry[]의 크기를 2로 둠.
//int dirx[] = {1, -1, 0, 0}; int diry[] = {0, 0, 1, -1}; 로 작성해도 무방할 듯
int dirx[] = {1, 0};
int diry[] = {0, 1};

for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            for(int k = 0; k < 2; k++)
            {
                int di = i + dirx[k];
                int dj = j + diry[k];

                if(di < 0 || di >= n || dj < 0 || dj >= m)
                    continue;
                pq.push({abs(stage[i][j]-stage[di][dj]), i*m+j, di*m+dj});
                //vector에 담고 정렬해도 무방.
            }

 

 

2. Union 함수 작성

void comb(int a, int b, int d, int t)
{
    //a, b: 두 노드 번호
    //d: 간선의 가중치
    //t: 문제에서 주어진 T
    //v[i]: i번 노드를 포함하는 컴포넌트. 이 벡터 안에는 컴포넌트를 구성하는 노드들이 들어있음.
    a = find(a);
    b = find(b);

    if(a == b)
        return;
    if(v[a].size() < v[b].size())
        swap(a, b);
    
    //afin: v[a]의 크기가 이미 t이상인가?
    //bfin: v[b]의 크기는 원래 t 미만이었는데, 이 union으로 인해 크기가 t이상으로 되는가?
    bool afin = 0, bfin = 0; 
    if(v[a].size() >= t)
        afin = 1;
    if(v[b].size() < t && v[a].size()+v[b].size() >= t)
        bfin = 1;
    
    //v[a]에 들어있는 원소들도 처음 difficulty rating이 매겨짐
    if(!afin && bfin)
        for(int x : v[a])
            val[x] = d;
    for(int x : v[b])
    {
        v[a].push_back(x);
        //v[b]애 들어있는 원소들이 처음 difficulty rating이 매겨짐
        if(bfin)
            val[x] = d;
    }

    v[b].clear();
    parent[b] = a;
}