반응형
https://www.acmicpc.net/problem/14868
14868번: 문명
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int n, k, area = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int arr[2001][2001];
int unf[100001];
int Find(int x) {
if (unf[x] < 0) return x;
return unf[x] = Find(unf[x]);
}
void merge(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
unf[x] = y;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
memset(unf, -1, sizeof(unf));
int t = 0;
int comp;
queue<pair<int, int> > Q;
queue<int> region;
cin >> n >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
arr[a][b] = ++area;
region.push(area);
comp = arr[a][b];
Q.push({ a,b });
}
int q = Q.size();
for (int i = 0; i < q; i++) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
if (arr[nx][ny] > 0) {
merge(arr[x][y], arr[nx][ny]);
}
}
Q.push({ x,y });
}
while (!region.empty() && Find(comp) == Find(region.front())) {
region.pop();
}
if (region.empty()) {
cout << t << '\n';
return 0;
}
while (!Q.empty()) {
int q = Q.size();
for (int i = 0; i < q; i++) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
if (arr[nx][ny] == 0) {
arr[nx][ny] = arr[x][y];
Q.push({ nx, ny });
}
else if (Find(arr[x][y]) != Find(arr[nx][ny])) {
merge(arr[x][y], arr[nx][ny]);
}
}
}
t++;
//인접한 곳에 union 되지 않은 영역 있는지 체크
q = Q.size();
for (int i = 0; i < q; i++) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
if (arr[nx][ny] > 0) {
merge(arr[x][y], arr[nx][ny]);
}
}
Q.push({ x,y });
}
while (!region.empty() && Find(comp) == Find(region.front())) {
region.pop();
}
if (region.empty()) {
cout << t << '\n';
return 0;
}
}
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 11085번 : 군사 이동 - Union & Find (0) | 2022.03.01 |
|---|---|
| 백준 3197번 : 백조의 호수 BFS Union&Find C++ (0) | 2022.03.01 |
| 백준 1178번 : 간선 추가 - 오일러 경로 , Union&Find 알고리즘 (0) | 2022.02.28 |
| 백준 16168번 : 퍼레이드 - 오일러 회로 C++ (0) | 2022.02.28 |
| 백준 1199번: 오일러 회로 시간초과 해결 (0) | 2022.02.28 |
