백준 14868 - 문명(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14868

14868번: 문명

어려웠던 그래프 문제입니다.

해당 문제는 BFS와 Union-Find를 같이 사용해 푸는 문제입니다.

BFS만을 통해 풀 수 있는 문제이긴 하지만 N,K값이 크기에 시간 초과가 생길 확률이 높습니다.

 

문제를 풀기 위해서는 2가지 함수를 만들어야합니다.

1. 문명을 연결하는 함수

2. 문명을 전파하는 함수

 

1번인 문명을 연결하는 함수의 경우에는 4방향 탐색을 통해 갈 수 있는 서로 다른 문명을 연결해주는 역할을 합니다.

2번인 문명을 전파하는 함수의 경우에는 4방향 탐색을 통해 비어있는 곳에 자신의 문명을 전파하는 역할을 합니다.

 

문제에서는 문명의 발상지가 주어집니다. 따라서 해당 발상지들을 탐색해 다른 발생지와 연결될 수 있는지를 먼저 확인해야합니다.

 

1. 문명을 연결하는 함수 - merge_city()

해당 문명에서 갈 수 있는 곳은 상하좌우 4방향입니다. 

먼저 현재 문명에서 비어있는 문명으로 전파를 해야합니다. 따라서 먼저 bfs()에 사용할 queue에 넣어줍니다.

따라서 4방향을 먼저 탐색해줍니다.

문명이 서로 연결될 경우는 두 좌표가 다른 문명일 경우입니다.

따라서 탐색할 곳이 Map의 범위 안이며, 다른 문명일 경우 연결해줍니다.

 

여기서 생각해봐야할 것이 있습니다.

예를 들어 X, Y문명이 각각 Z라는 같은 문명과 연결되어 있다고 가정해봅시다. 그렇다면 X, Y문명은 Z문명을 통해 서로 이동할 수 있습니다. 

즉, 서로 다른 문명이더라도 연결된 문명이 같다면 두 문명을 연결할 필요가 없다는 뜻입니다.

이를 정리해보자면

 

두 문명을 연결할 경우는

1. 탐색할 곳이 Map의 범위 안에 있으며

2. 서로 다른 문명이여야 하고

3. 서로 연결된 문명도 달라야한다.

-> 해당 경우를 만족하는 경우에만 두 문명을 합쳐줍니다. 두 문명을 합쳐줬으니 문명의 수를 하나 빼줍니다. 

 

2. 문명을 전파하는 함수 - bfs()

현재 문명에서 4방향을 확인해봅니다.

문명을 전파하는 것은 빈 곳에 자신의 문명을 전파하는 것을 의미합니다.

따라서 탐색할 좌표에 문명이 없는 경우(Map의 값이 0)에 자신의 문명을 전파합니다.

전파된 문명에서는 4방향 탐색을 통해 다른 문명과 연결할 수 있는지 확인해야하니 city queue에 넣어줍니다.

 

코드가 끝나는 경우는 문명이 전부 합쳐져 K의 값이 1이 되는 경우입니다.

해당 경우에 걸린 시간을 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
#define INF 987654321
#define P pair<int,int>

using namespace std;

int N, K;
int map[2001][2001];
int connect[100001];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
queue<P> city;
queue<P> q;

int Find(int x){
	if(connect[x] == x) return x;
	else return connect[x] = Find(connect[x]);
}

void Union(int x, int y){
	int X = Find(x);
	int Y = Find(y);
	if(X != Y){
		connect[X] = Y; 
	}
}

void merge_city(){
	while(	!city.empty()){
		int x = city.front().first;
		int y = city.front().second;
		q.push({x, y});
		city.pop();
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			int now_civil = map[x][y];
			int next_civil = map[xx][yy];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){
				if(map[xx][yy] != 0){
					if(now_civil != next_civil && Find(now_civil) != Find(next_civil)){
						Union(now_civil, next_civil);
						K--; // 문명이 합쳐졌으니 1 감소
					}	
				}
			}
		}
	}
}

void bfs(){
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){
				if(map[xx][yy] == 0){
					map[xx][yy] = map[x][y];
					city.push({xx,yy});
				}
			}
		}
	}
}

void solve(){
	int time_ = 0;
	while(K > 1){
		merge_city();
		if(K == 1){
			cout << time_;
			break;
		}
		bfs();
		time_++;
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for(int i = 0; i < K; i++){
		int x, y;
		cin >> x >> y;
		map[x][y] = i+1;
		city.push({x,y});
	}
	for(int i = 1; i <= K; i++) connect[i] = i;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요