백준 3197번: 백조의 호수
25643 단어 Union FindpsBFScppDisjointSetBFS
백조의 호수
아이디어
문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ;
맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다.
코드
#include <bits/stdc++.h>
using namespace std;
const int dy[4] = {1, -1, 0, 0};
const int dx[4] = {0, 0, 1, -1};
int N, M;
int arr[2000][2000];
int p[4000000];
vector<pair<int, int>> v;
vector<pair<int, int>> sv;
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
p[n1] += p[n2];
p[n2] = n1;
}
bool check() {
int np = find(M*v[0].first+v[0].second);
for (auto p : v) {
if (find(M*p.first+p.second) != np) return false;
}
return true;
}
int bfs() {
queue<pair<int, int>> q;
for (auto p : sv) {
q.push({p.first, p.second});
for (int i = 0; i < 4; i++) {
int ny = p.first + dy[i];
int nx = p.second + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) Union(M*ny+nx, M*p.first+p.second);
}
}
if (check()) return 0;
int year = 1;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int y = cur.first;
int x = cur.second;
if (year != arr[y][x]) {
if (check()) return year;
year++;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) continue;
arr[ny][nx] = arr[y][x] + 1;
for (int j = 0; j < 4; j++) {
int nny = ny + dy[j];
int nnx = nx + dx[j];
if (nny >= N || nny < 0 || nnx >= M || nnx < 0) continue;
if (arr[nny][nnx] != 0) {
Union(M*nny+nnx, M*ny+nx);
}
}
q.push({ny, nx});
}
}
return year;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
char x;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> x;
if (x == 'L') {
arr[i][j] = 1;
v.push_back({i, j});
sv.push_back({i, j});
}
else if (x == 'X') {
arr[i][j] = 0;
}
else if (x == '.') {
arr[i][j] = 1;
sv.push_back({i, j});
}
}
}
memset(p, -1, sizeof(p));
cout << bfs();
return 0;
}
여담
이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.
Author And Source
이 문제에 관하여(백준 3197번: 백조의 호수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-3197번-백조의-호수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)