[백준] 14868 - 문명 (P4)
https://www.acmicpc.net/problem/14868
풀이 과정
시드마이어의 문명과 비슷한 게임을 구현하는 시뮬레이션 문제
문명이 건설되었을 때, 시간이 지남에 따라 점점 퍼지다가 두 문명이 인접하면 하나의 문명으로 합쳐진다.
이때 모든 문명이 하나로 합쳐지기까지 걸리는 시간을 구하는 문제이다.
문명이 건설되었을 때 퍼지는 것은 BFS로 구현할 수 있고, 문명을 하나의 그룹으로 합치는 것은 분리집합으로 구현할 수 있다.
(분리집합을 사용하지 않고도 풀 수 있다는데, 그렇게는 안 풀어봤다.)
from collections import deque
import sys
input = sys.stdin.readline
def find(x):
if parent[x] == x:
return x
parent[x] = find(parent[x])
return parent[x]
def union(x1, x2):
global group_count
x1 = find(x1)
x2 = find(x2)
if x1 != x2:
parent[x1] = x2
group_count -= 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
우선 BFS, Union Find 를 사용할 때 필요한 변수와 함수를 만들어준다.
n, k = map(int, input().split())
board = [[-1 for _ in range(n)] for _ in range(n)]
parent = [i for i in range(k)]
group_count = k
year = 0
다음으로 입력을 받는데, 중요한 것은 group_count 변수이다.
union find 에서 union 연산을 수행할 때마다 group 개수는 1개씩 줄어든다.
문제에서 구하는 모든 문명이 하나로 합쳐지는 시간은 group_count 값이 1이 되기까지의 시간을 말한다.
year 은 그 시간(년수)에 대한 변수이다.
나는 정말 나이브하게 문제를 풀었다.
문제를 읽어보면
1. 모든 문명은 매년 상하좌우로 인접한 곳으로 퍼지고
2. 퍼진 곳 또는 퍼진 곳과 상하좌우 인접한 곳에 다른 문명이 있으면 해당 문명과 하나로 합쳐진다
라고 했다.
즉 한 해 동안 일어나는 일은
1. 인접한 곳으로 퍼지기
2. 인접 문명과 합치기
가 일어나는 것이다.
그리고 인접 문명과 합치기 과정을 끝냈을 때 group_count = 1 이면 그때까지의 시간을 출력하면 된다.
이때 처음에 문명을 입력받고, 해당 문명에 대해서 인접한 문명끼리는 바로 합쳐야 하는데,
이 부분만 따로 떼어내서 구현하고, 그 뒤로는 반복문을 통해 구현하였다.
d = deque()
for i in range(k):
x, y = map(int, input().split())
d.append((x-1, y-1))
board[x-1][y-1] = i
for now_x, now_y in d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] != -1:
union(board[next_x][next_y], board[now_x][now_y])
BFS를 돌 때 board 를 -1로 초기화했다가 문명이 퍼지면 해당 문명 번호로 board 를 채워서 board 배열 값이 -1 인지 아닌지로 visit 여부를 체크했다.
먼저 문명 별 위치 정보를 받아서 board 에 해당 문명 번호를 표시하고, 덱에도 추가해준다.
그리고 (덱의 원소를 빼지 않고) 덱을 순회하면서 0년도 문명 상태에 대해서 인접 문명들을 하나로 합쳐준다.
while group_count > 1:
new_d = deque()
for now_x, now_y in d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] == -1:
new_d.append((next_x, next_y))
board[next_x][next_y] = board[now_x][now_y] # 현재 문명으로 방문
for now_x, now_y, now_year in new_d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] != -1:
union(board[next_x][next_y], board[now_x][now_y])
year += 1
d = new_d
다음으로 group_count 가 1보다 큰 동안 반복을 돈다.
만약 0년도 문명 상태에 대해서 인접 문명들이 모두 하나로 합쳐졌다면 group_count = 1 이 되어 반복문을 돌지 않는다.
1. 문명 퍼뜨리기
나는 매 년도마다 문명 상태를 따로 관리하기 위해서 새로운 년도에 대해서 새로운 덱을 사용하여 순회하였다.
기존 덱을 순회하면서 문명들을 퍼뜨리고, 이렇게 새로 퍼뜨려진 문명 정보는 기존 덱이 아니라 새로운 덱에 추가한다.
그래야 퍼지기 전에 존재했던 영역과 이번에 새로 퍼진 영역을 구분할 수 있기 때문이다.
2. 인접 문명 체크하기
새롭게 퍼진 영역 (new_d) 를 순회하면서 각 새로운 영역의 인접한 곳에 기존 문명이 있는지 확인한다.
기존 문명이 있다면 union 연산을 통해 하나로 합쳐준다.
이 과정이 끝나면 연도가 하나 증가하고,
기존의 덱을 새로 만든 덱으로 교체한다.
이 과정을 group_count > 1 인 동안에 계속 반복하고, group_count = 1 이 되면 반복문을 나와서 year 값을 출력하면 된다.
파이썬 정답 코드
from collections import deque
import sys
input = sys.stdin.readline
def find(x):
if parent[x] == x:
return x
parent[x] = find(parent[x])
return parent[x]
def union(x1, x2):
global group_count
x1 = find(x1)
x2 = find(x2)
if x1 != x2:
parent[x1] = x2
group_count -= 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, k = map(int, input().split())
board = [[-1 for _ in range(n)] for _ in range(n)]
parent = [i for i in range(k)]
group_count = k
year = 0
d = deque()
for i in range(k):
x, y = map(int, input().split())
d.append((x-1, y-1, 1))
board[x-1][y-1] = i
for now_x, now_y, now_year in d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] != -1:
union(board[next_x][next_y], board[now_x][now_y])
while group_count > 1:
new_d = deque()
for now_x, now_y in d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] == -1:
new_d.append((next_x, next_y))
board[next_x][next_y] = board[now_x][now_y] # 현재 문명으로 방문
for now_x, now_y in new_d:
for k in range(4):
next_x, next_y = now_x + dx[k], now_y + dy[k]
if 0 <= next_x < n and 0 <= next_y < n:
if board[next_x][next_y] != -1:
union(board[next_x][next_y], board[now_x][now_y])
year += 1
d = new_d
print(year)
C++ 정답 코드
#include <iostream>
#include <deque>
using namespace std;
typedef long long ll;
ll n, k, group_count;
ll board[2000][2000];
ll parent[100000]; k = {0 , 1, 2, . ... k}
ll dx[4] = {-1, 1, 0, 0};
ll dy[4] = {0, 0, -1, 1};
void print_board() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << board[i][j] << " ";
}
cout << '\n';
}
}
ll find(ll x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
void merge(ll x, ll y) {
x = find(x);
y = find(y);
if (x != y) {
parent[x] = y;
group_count--;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
/**
* init
*/
cin >> n >> k;
deque<pair<ll, ll>> d;
group_count = k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = -1;
}
}
for (int i = 0; i < k; i++) {
parent[i] = i;
}
/**
* logic
*/
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
board[x-1][y-1] = i;
d.emplace_back(x-1, y-1);
}
for (auto p : d) {
for (int k = 0; k < 4; k++) {
ll next_x = p.first + dx[k];
ll next_y = p.second + dy[k];
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
if (board[next_x][next_y] != -1) {
merge(board[next_x][next_y], board[p.first][p.second]);
}
}
}
}
int year = 0;
while (group_count > 1) {
// 확장
deque<pair<ll, ll>> new_d;
for (auto p : d) {
for (int k = 0; k < 4; k++) {
ll next_x = p.first + dx[k];
ll next_y = p.second + dy[k];
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
if (board[next_x][next_y] == -1) {
board[next_x][next_y] = board[p.first][p.second];
new_d.emplace_back(next_x, next_y);
}
}
}
}
for (auto p : new_d) {
for (int k = 0; k < 4; k++) {
ll next_x = p.first + dx[k];
ll next_y = p.second + dy[k];
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
if (board[next_x][next_y] != -1) {
merge(board[next_x][next_y], board[p.first][p.second]);
}
}
}
}
d = new_d;
year += 1;
}
cout << year << '\n';
return 0;
}