[C++][백준] 문명(14868)

문제

인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다. 여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.

세계를 N×N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 형태로 생각할 수 있다. 가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N) 위치에 있다. 두 정사각형 (a,b)와 (a′,b′)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.

• |a-a′| = 1 이고 b = b′.
• |b-b′| = 1 이고 a = a′.

문명의 최초 발상지는 모두 서로 다른 K곳에 있다. 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다. 문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다. 한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 정사각형 (a,b)가 문명 지역이면, 다음 해에는 세계의 경계를 넘지 않는 한 이 정사각형과 인접한 네 정사각형 (a+1,b), (a-1,b), (a,b+1), (a,b-1)에 문명이 전파된다. 만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.

예를 들어, 다음과 같이 5×5 크기의 세계에 4곳의 정사각형 (1,1), (2,1), (2,5), (5,2)가 문명의 발상지라고 하자. 정사각형 (1,1), (2,1)의 문명은 인접해 있으므로 처음부터 결합되어 있다. 1년후 문명이 전파된 지역은 오른쪽 그림과 같고, 2년 후에 문명이 전파된 지역은 아래 그림과 같다. 이때 모든 문명은 서로 결합되어 하나의 문명이 된다. (2,5)에서 발상한 문명과 (5,2)에서 발상한 문명은 직접적으로 결합되지는 않았지만, (1,1),(2,1)에서 발상한 문명을 통하여 결합됨에 주의하라.

세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.

 

출력

표준 출력으로 모든 문명이 하나로 결합되는데 걸리는 최소 햇수를 정수로 출력한다.

 

풀이

해당 문제는 BFS + 유니온파인드를 이용해 풀이하였습니다.

 

2차원 배열의 인덱스 (x, y)를 (x * N + y + 1) 식을 사용하여 Integer 인덱스로 변환합니다.

 

문제에서 문명 최초 발상지끼리 인접해있다면 이들은 처음부터 하나로 결합된다고 설명하고 있습니다. 

처음부터 연결된 케이스를 고려하기 위해 최초 문명 발상를 입력받을 때 인접한 곳에 다른 최초 문명이 있는지 확인하고 있다면 결합(union) 시켜줍니다.

 

그 다음부터는 year를 증가해주면서 아래 로직을 수행합니다.

1) 모든 문명이 하나로 결합되었는지 확인합니다.

 - K개의 최초 문명 발상지가 하나로 결합되었는지 확인하면 됩니다. K개의 최고 조상노드가 일치하는지 확인합니다.

2) 인접해있으면서 아직 방문하지 않은 지역을 결합(union)합니다.

3) 2)번 지역과 맞닿은 다른 문명이 있는지 확인합니다. 있다면 결합(union)합니다.

 

해당 로직은 아래 두 케이스 모두 커버할 수 있습니다.

 

케이스1)

케이스2)

 전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 2010;
bool visited[MAX][MAX];
int N, K;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

int parent[MAX * MAX];
vector<int> baseCountries;

struct myData {
	int x;
	int y;
};

void init() {
	for (int i = 0; i < MAX * MAX; i++) {
		parent[i] = -1;
	}
}

int find(int n) { // 노드 n의 최고 조상 노드를 찾는 함수
	if (parent[n] < 0) return n;

	parent[n] = find(parent[n]);
	return parent[n];
}

void unions(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) return;
	parent[b] = a;
}

int changeNum(int x, int y) {
	return x * N + y + 1;
}

bool isInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	else return false;
}

bool checkAllConnected() {
	int p = find(baseCountries[0]);
	for (int i = 1; i < baseCountries.size(); i++) {
		if (p != find(baseCountries[i])) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> N >> K;

	queue<myData> myQueue;
	init();
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;

		myQueue.push({ x, y });
		visited[x][y] = true;

		int baseCountry = changeNum(x, y);
		baseCountries.push_back(baseCountry);

		for (int j = 0; j < 4; j++) {
			int nextX = x + dirX[j];
			int nextY = y + dirY[j];

			if (isInRange(nextX, nextY) && visited[nextX][nextY] == true) {
				int nextCountry = changeNum(nextX, nextY);
				unions(baseCountry, nextCountry);
			}
		}
	}

	int year = 0;
	while (1) {
		if (checkAllConnected()) break;

		queue<myData> myQueue2;
		while (!myQueue.empty()) {
			int curX = myQueue.front().x;
			int curY = myQueue.front().y;
			myQueue.pop();
			int baseCountry = changeNum(curX, curY);

			for (int i = 0; i < 4; i++) {
				int nextX = curX + dirX[i];
				int nextY = curY + dirY[i];

				if (isInRange(nextX, nextY) && visited[nextX][nextY] == false) {
					int nextCountry = changeNum(nextX, nextY);
					unions(baseCountry, nextCountry);

					visited[nextX][nextY] = true;
					myQueue2.push({ nextX, nextY });

					for (int j = 0; j < 4; j++) {
						int connectedX = nextX + dirX[j];
						int connectedY = nextY + dirY[j];

						if (isInRange(connectedX, connectedY) && visited[connectedX][connectedY] == true) {
							int connectedCountry = changeNum(connectedX, connectedY);
							if (baseCountry != connectedCountry) unions(baseCountry, connectedCountry);
						}
					}
				}
			}
		}
		year++;
		myQueue = myQueue2;
	}

	cout << year;
	return 0;
}