문제요약
2차원 배열 상에서 인구이동이 몇 번 이루어질 수 있는지 시뮬레이션 하세요.
각 배열 칸은 나라이며, 상하좌우로 인접한 칸들은 국경선을 공유하는 나라입니다.
참고로 인구 이동은 오늘부터 시작하고, 인구 이동이 없어질 때까지 진행하면 됩니다.
인구이동 1회 당...
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
인풋
- N : 대륙의 크기(1 ≤ N ≤ 50). 대륙은 N*N크기의 배열로 이루어져있다.
- L,R : 국경선을 열지 결정하는 데 참고할 상수
- 2차원 배열(N*N) : 각 칸 별 사람 수
단, 인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.
아웃풋
인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.
아이디어
그냥 정확한 시뮬레이션
헷갈렸던 점
문제 상에선 열 수 있는 국경선을 모두 열어두고 연합 별 평준화 작업을 하라고 한다.
이 말만 보고
1. 열 수 있는 모든 국경선 열고 저장하기
2. 1번에서 정리 해둔 것을 참고하며 BFS하면서 component 저장
3. 2번에서 얻은 연합들에 대해 평준화 작업
이렇게 하려고 계획했었다.
근데 1번 2번을 나누는 게 큰 의미가 없다. 왜냐하면 2번을 할 때 bfs가 끝나자 마자 인구 수를 수정하는 게 아니고, bfs가 모든 seed(pivot)에 대해 끝났을 때 인구 수를 수정하기 때문이다.
그래서 1번을 없애고, 2번에서 BFS를 할 때 adjacent 조건(같은 component로 취급할 수 있는 조건)에서 L과 R을 활용한 조건으로 적용했다.
삽질
시간초과 : seed 구하기
모든 seed에 대해 component를 매 시뮬레이션 단계(level)마다 구한다.
나의 경우 seed(코드 상 pivot)을 구하는 부분을 2차원 배열을 처음부터 끝까지 순회하는 방법으로 구현했다. 이렇게 했을 때 seed를 바꿀 때(level이 바뀐 건 아니다) 이미 검사한 2차원 배열의 윗부분을 다시 검사해주는 문제가 생긴다. 그래서 같은 시뮬레이션 레벨이면 이전 seed 다음부분부터 검사하는 방법으로 개선을 해서 통과할 수 있었다.
반면 모든 component를 구하는 bfs는 크게 문제가 되지 않는다. 어차피 모든 vertice를 방문하는 거니까.... bfs의 O(vertice 개수+E) = O(vertice 개수+4vertice 개수)일 것이다.(E는 각 vertice마다 4개의 인접 vertice를 검사하기 때문)
vertive 개수가 최대 100*100이긴한데... 배열이라 빠르게 동작하는 거 같다.
소스코드
#include<iostream>
#include<math.h>
#include<queue>
#include<memory.h>
using namespace std;
int tab[100][100];
int former[100][100];
int visited[100][100];
int n, l, r;
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
struct pos {
int i, j;
};
bool inbox(int i, int j) {
return i >= 0 && i < n&& j >= 0 && j < n;
}
pos pick_piv() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == 0) {//0명인 국가도 가능
return pos{ i,j };
}
}
}
return pos{ -1, -1 };
}
void init_visited() {
memset(visited, 0, sizeof(visited));
}
void bfs(int ctr, pos piv) {
queue<pos> q;
q.push(piv);
visited[piv.i][piv.j] = ctr;
//print_visited();
while (!q.empty()) {
pos cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int ci = cur.i + di[k], cj = cur.j + dj[k];
if (inbox(ci, cj)) {//0명인 국가도 가능
int s = abs(tab[cur.i][cur.j] - tab[ci][cj]);
if (s >= l && s <= r && visited[ci][cj] == 0) {
q.push(pos{ ci, cj });
visited[ci][cj] = ctr;
}
}
}
//print_visited();
}
}
bool issame() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (former[i][j] != tab[i][j]) {
return false;
}
}
}
return true;
}
void med_tab() {
int sum_idx[100 * 100];
int reg_idx[100 * 100];
memset(sum_idx, 0, sizeof(sum_idx));
memset(reg_idx, 0, sizeof(reg_idx));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum_idx[visited[i][j]] += tab[i][j];
reg_idx[visited[i][j]]++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int med_val = sum_idx[visited[i][j]] / reg_idx[visited[i][j]];//소숫점 버림
tab[i][j] = med_val;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
cin >> l >> r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> tab[i][j];
}
}
//시뮬
int level = 0;
for (; level <= 2000; level++) {
memcpy(&former[0][0], &tab[0][0], sizeof(tab));
init_visited();
pos piv = pick_piv();
int ctr = 1;
//현재 인구수 기준으로 bfs 컴포넌트 구해둠
while (piv.i != -1) {
//cout <<"level : "<<level<<" , ctr : "<<ctr<< " , pivot : " << piv.i << " " << piv.j << endl;
bfs(ctr, piv);
ctr++;
piv = pick_piv();
}
med_tab();
//print_tab();
if (issame()) {
break;
}
}
cout << level;
}