[백준 9879] Cross Country Skiing

문제 링크 : 9879번: Cross Country Skiing (acmicpc.net)

9879번: Cross Country Skiing

 

"Disjoint set" 을 이용한 문제이다.

 

인풋으로 elevation 과 waypoint 가 주어질 때, 특정 waypoint 에서 모든 waypoint 으로 이동할 수 있도록 하는 D 의 최솟값을 구하는 문제이다.

문제에 주어진 인풋을 예로 들어서 어떻게 접근해야 할지 살펴보도록 한다.

 

※ 문제 접근 방법

 

① 인풋으로 주어진 elevation 과 waypoint 를 기반으로 하여 아래와 같이 그래프로 나타내도록 한다.

 

 

이때 waypoint 마다 색이 다른 것을 알 수 있는데 이는 서로 독립된 집합임을 나타내기 위함이다.

그렇다면, 위와 같은 정보를 담기 위해서 현재 정점, 인접한 정점, 거리를 담을 수 있는 벡터를 다음과 같이 정의한다.

vector<pair<int, pair<int, int>>> info : {거리, {현재 정점, 인접한 정점}} 

 

주어진 elevation 정보를 통해 거리(dist)를 현재 정점(cur)과 인접한 정점(next)을 갖고 다음과 같이 정의할 수 있다.

dist = | elevation(cur) - elevation(next) |   

 

② 위에서 거리, 현재 정점, 인접한 정점을 모두 info 에 담았다고 한다면, 거리가 오름차순이 되도록 정렬한다.

이제 Disjoint set 을 이용하기 위해 아래와 같은 2가지 배열을 이용하여 해결하도록 하였다.

 

• int parent[x] : 정점 x가 속한 그룹은 parent[x] 이며, 정점 x가 waypoint 에 속한 그룹일 때 parent[x] = 0 으로 설정 (0 ≤ parent[x] ≤ M * N)
• int check[x] : 정점 x가 속한 그룹은 check[x] 으로 설정 (1 ≤ check[x] ≤ M * N)

 

parent 배열은 특별하게도 어떤 정점 x가 속한 그룹이 waypoint 에 속한 그룹인 경우를 강조하기 위해 선언하였다. 

아래 코드와 같이 parent 배열과 check 배열을 초기화 할 수 있다.

void set_parent(int parent[])
{
	for (int i = 1; i <= R * C; i++)
	{
		if (point[i]) parent[i] = 0;
		else parent[i] = i;
	}
}

void set_check(int check[])
{
	for (int i = 1; i <= R * C; i++)
		check[i] = i;
}

 

그리고, parent 배열을 통해 waypoint 에 속한 그룹이 다음과 같이 묶이는 것을 알 수 있다.

 

③ 크루스칼 알고리즘을 통해 MST 를 구하는 방법을 활용하여 D 값을 갱신할 수 있다.

우선, waypoint 끼리 cycle 이 되지 않도록 연결될 때를 카운팅하기 위한 변수 connect 를 선언하였다.

connect 값이 (waypoint 의 갯수 - 1) 이 될 때까지 D 값을 갱신해서 결과를 도출할 수 있다.

 

 connect == (waypoint 의 갯수 - 1) 일 때까지 D 값을 갱신하는 이유는?

 

위 경우는 서로 다른 waypoint 그룹이 하나의 waypoint 그룹으로 이뤄진 경우이다.

즉, 쉽게 말해서 서로 다른 waypoint 의 그룹이 (waypoint 의 갯수 - 1) 만큼 cycle 없이 연결된 경우로 트리임을 짐작할 수 있다.

 

그렇다면 정점 x, 정점 y, 그리고 두 정점 사이의 거리 dist 를 통해 두 정점 x, y 가 속한 그룹이 동일하지 않으면 두 정점의 그룹을 동일하게 하면서 D 값을 주어진 dist 를 통해 갱신할 수 있다.

이때 핵심은 두 정점이 속한 그룹이 waypoint 에 속한 그룹이라면, 두 waypoint 의 그룹이 동일하지 않을 때 두 그룹을 합치고 connect 값을 증가시키며 동일할 경우는 cycle 이 발생하므로 합치지 않으면 된다. 

 

 이에 대한 플로우는 다음과 같다.

 

거리가 1 인 경우에 대해서 그룹화 한 결과는 다음과 같다.

 

 

위와 같이 가장 작은 거리부터 시작하여 두 정점에 속한 그룹을 동일하게 하면서 D 값을 갱신하였다. 

계속해서 살펴보도록 한다.

 

거리가 2 인 경우에 대해서 그룹화 한 결과는 다음과 같다.

 

 

거리가 3 인 경우에 대해서 그룹화하려고 하지만 cycle 이 발생하기 때문에 이는 무시한다.

거리가 4, 5, ..., 20 인 경우에 대해서 그룹화 한 결과를 본다.

 

 

아직 거리 20 에 대해 완전히 그룹화하지 않았다.

위와 같이 빨간색인 그룹과 초록색인 그룹이 결국 waypoint 에 대한 그룹으로 해당 그룹을 그룹화한다면 다음과 같아진다.

 

 

그리고 거리 21에 대해 그룹화하게 된다면 다음과 같아진다.

 

 

connect 값이 이제 (waypoint 의 갯수 - 1) 가 되었으므로 종료한다.

그리고 D 값을 출력하면 된다.

 

이에 대한 코드는 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <math.h>

#define ll long long

using namespace std;

int R, C, P;
int dx[2] = { 1, 0 };
int dy[2] = { 0, 1 };
int elev[501][501];
int point[250001], parent[250001], check[250001];

void input()
{
	int cnt = 0;

	cin >> R >> C;
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			cin >> elev[i][j];
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			cin >> point[++cnt];
			if (point[cnt])
				P++;
		}
	}
}

int get_vertex(int x, int y)
{
	return ((x - 1) * C + y);
}

bool compare(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y)
{
	return (x.first < y.first);
}

void set_info(vector<pair<int, pair<int, int>>>& info)
{
	for (int x = 1; x <= R; x++)
	{
		for (int y = 1; y <= C; y++)
		{
			for (int i = 0; i < 2; i++)
			{
				int next_x = x + dx[i], next_y = y + dy[i];
				if (next_x >= 1 && next_x <= R && next_y >= 1 && next_y <= C)
				{
					int dist = abs(elev[next_x][next_y] - elev[x][y]);
					info.push_back({ dist, {get_vertex(x, y), get_vertex(next_x, next_y)} });
				}
			}
		}
	}
	sort(info.begin(), info.end(), compare);
}

void set_parent(int parent[])
{
	for (int i = 1; i <= R * C; i++)
	{
		if (point[i]) parent[i] = 0;
		else parent[i] = i;
	}
}

void set_check(int check[])
{
	for (int i = 1; i <= R * C; i++)
		check[i] = i;
}

int get_parent(int x, int parent[])
{
	if (x == parent[x])
		return x;
	return (parent[x] = get_parent(parent[x], parent));
}

void go_union(int x, int y, int parent[])
{
	x = get_parent(x, parent);
	y = get_parent(y, parent);
	if (x > y) 
		parent[x] = y;
	else
		parent[y] = x;
}

void solution()
{
	vector<pair<int, pair<int, int>>> info;
	int D = 0, connect = 0;
	int from, to, dist, from_parent, to_parent;
	int from_check, to_check;

	set_info(info);
	set_parent(parent);
	set_check(check);
	for (int i = 0; i < info.size(); i++)
	{
		from = info[i].second.first, to = info[i].second.second, dist = info[i].first;
		from_parent = get_parent(from, parent), to_parent = get_parent(to, parent);
		from_check = get_parent(from, check), to_check = get_parent(to, check);
		if (from_parent != to_parent)
		{
			go_union(from, to, parent);
			go_union(from, to, check);
		}
		else if(from_parent == 0 && to_parent == 0)
		{
			if (from_check != to_check)
			{
				go_union(from, to, check);
				connect++;
			}
		}
		D = max(D, dist);
		if (connect == P - 1)
			break;
	}
	cout << D;
}

int main()
{
	input();
	solution();

	return 0;
}