백준 14868 문명 (c++) : 피너클

14868번: 문명

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

 

bfs와 유니온 파인드로 풀었다.

 

int n, k, cnt = 0;
int parent[2001 * 2001];
int arr[2001][2001];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

사용할 변수들이다.

arr[10][10]의 parent는 parent[10 * 2001 + 10] 이런식으로 나타낼것이다.

int union_find(int v) {
	if (parent[v] == v) return v;
	else return parent[v] = union_find(parent[v]);
}

일반적인 유니온 파인드 코드다.

void union_make(int u, int v) {
	u = union_find(u);
	v = union_find(v);

	if (u == v) return;

	if (u < v) parent[v] = u;
	else parent[u] = v;
}

이것도

void merge(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
			if (arr[ny][nx] != -1) {
				if (union_find(ny * 2001 + nx) != union_find(y * 2001 + x)) {
					union_make(ny * 2001 + nx, y * 2001 + x);
					cnt--;
				}
			}
		}
	}
}

merge 함수는 y, x에 인접한 지역들을 확인하며 자신과 parent가 다를 경우 합쳐주는 역할을 한다.

이때 합치는 경우 cnt--를 해준다. cnt는 존재하는 문명의 개수이다.

cnt가 1이 되면 존재하는 문명이 1개라는 의미이다.

	memset(arr, -1, sizeof(arr));
	memset(parent, -1, sizeof(parent));

	queue<pair<pair<int, int>, int>> q;

	cin >> n >> k;
	cnt = k;

기본 입력과 초기화를 해주고 cnt=k로 해준다.

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;

		arr[a][b] = 1;
		parent[a * 2001 + b] = a * 2001 + b;

		merge(a, b);

		q.push({ {a, b}, 0 });
	}

그 후 초기 문명이 있는 위치를 받으며

문명들을 선언해주고

merge로 인접한 곳에 문명이 있는 경우 합쳐준다.

이렇게 하면 초기에 붙어있는 문명도 전부 처리가 된다.

	int final_time = 0;

최종적으로 드는 시간을 담을 코드다.

	while (cnt > 1 && !q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int t = q.front().second;
	
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
				if (arr[ny][nx] == -1) {
					arr[ny][nx] = 1;
					parent[ny * 2001 + nx] = union_find(y * 2001 + x);

					merge(ny, nx);

					if (cnt == 1) {
						final_time = t + 1;
						break;
					}

					q.push({ {ny, nx}, t + 1 });
				}
				else {
					if (union_find(ny * 2001 + nx) != union_find(y * 2001 + x)) {

						union_make(ny * 2001 + nx, y * 2001 + x);
                        			cnt--;
						if (cnt == 1) {
							final_time = t + 1;
							break;
						}
					}
				}
			}
		}
	}

	cout << final_time << '\n';

그 후에는 그냥 bfs 돌려주면 된다.

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {

인접한 곳들을 확인해주며

				if (arr[ny][nx] == -1) {
					arr[ny][nx] = 1;
					parent[ny * 2001 + nx] = union_find(y * 2001 + x);

					merge(ny, nx);

					if (cnt == 1) {
						final_time = t + 1;
						break;
					}

					q.push({ {ny, nx}, t + 1 });
				}

만약 인접한 곳에 문명이 없다면 그곳을 현재 위치와 같은 문명으로 채워주고

인접한 곳에 다른 문명이 있는지 merge함수로 확인한다.

merge함수 안에 cnt--가 있으니 

만약 cnt가 1이 되었다면 final_time을 바꿔주고 break해준다.

				else {
					if (union_find(ny * 2001 + nx) != union_find(y * 2001 + x)) {

						union_make(ny * 2001 + nx, y * 2001 + x);
						cnt--;

						if (cnt == 1) {
							final_time = t + 1;
							break;
						}
					}
				}

만약 채워져 있는데 문명이 다르다면

union_make로 두 문명을 합쳐주고 cnt--를 한뒤 확인해준다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <tuple>

using namespace std;

int n, k, cnt = 0;
int parent[2001 * 2001];
int arr[2001][2001];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int union_find(int v) {
	if (parent[v] == v) return v;
	else return parent[v] = union_find(parent[v]);
}

void union_make(int u, int v) {
	u = union_find(u);
	v = union_find(v);

	if (u == v) return;

	if (u < v) parent[v] = u;
	else parent[u] = v;
}

void merge(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
			if (arr[ny][nx] != -1) {
				if (union_find(ny * 2001 + nx) != union_find(y * 2001 + x)) {
					union_make(ny * 2001 + nx, y * 2001 + x);
					cnt--;
				}
			}
		}
	}
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	memset(arr, -1, sizeof(arr));
	memset(parent, -1, sizeof(parent));

	queue<pair<pair<int, int>, int>> q;

	cin >> n >> k;
	cnt = k;

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;

		arr[a][b] = 1;
		parent[a * 2001 + b] = a * 2001 + b;

		merge(a, b);

		q.push({ {a, b}, 0 });
	}

	int final_time = 0;

	while (cnt > 1 && !q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int t = q.front().second;
	
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
				if (arr[ny][nx] == -1) {
					arr[ny][nx] = 1;
					parent[ny * 2001 + nx] = union_find(y * 2001 + x);

					merge(ny, nx);

					if (cnt == 1) {
						final_time = t + 1;
						break;
					}

					q.push({ {ny, nx}, t + 1 });
				}
				else {
					if (union_find(ny * 2001 + nx) != union_find(y * 2001 + x)) {

						union_make(ny * 2001 + nx, y * 2001 + x);
						cnt--;

						if (cnt == 1) {
							final_time = t + 1;
							break;
						}
					}
				}
			}
		}
	}

	cout << final_time << '\n';


	return 0;

}

전체코드다.