https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명
www.acmicpc.net
bfs 혹은 dfs를 활용하여 해결할 수 있다.
인구이동 조건과, 방문 여부가 탐색 진행의 기준이 된다.
for(for(bfs)) 구조로 해결할 수 있다.
for(for 을 완전히 탈출할 때 까지가 한 번의 인구이동 날이라고 할 수 있다.
따라서 이를 무한루프로 감싸서, 인구의 이동이 없는 경우 무한루프를 탈출하는 구조로 해결하면 된다.
그런데, 인구 이동 조건을 만족하더라도, 그 자리에서 인구수를 바로 갱신할 수가 없다.
일단 국경을 개방할 수 있는 지점을 모두 찾아내야 하기 때문에, 일단 한 번의 bfs가 다 종료되어야 인구수를 갱신할 수 있다. 방문처리된 지점들(큐에 삽입된 적이 있는 지점들)이 갱신의 대상이기 때문에, 이 좌표들을 차례로 백터에 저장해준다.
이후에 벡터의 크기가 연합국의 숫자이고, 인구수의 합은 큐에 삽입하면서 기억해 둘 것이다.
한번의 인구 이동이 모두 끝났는데, 변화가 없다면 무한 루프를 종료하고, 그렇지 않다면 방문처리 배열을 초기화해준 이후에 인구이동을 다시 시작해주면 된다.
#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int N, L, R, m[51][51];
bool bor[51][51]; //방문 처리 배열
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
queue<pair<int, int> > q;
bool updated = false;
int idxSum = 0;
vector<pair<int, int> > v;
void bfs(pair<int, int> start) {
q.push(start);
bor[start.first][start.second] = true;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N || bor[nr][nc])
continue;
if (abs(m[nr][nc] - m[cur.first][cur.second]) >= L &&
abs(m[nr][nc] - m[cur.first][cur.second]) <= R) {
q.push({ nr, nc });
bor[nr][nc] = true;
v.push_back({ nr, nc });
idxSum += m[nr][nc];
}
}
}
}
void init() {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
bor[i][j] = 0;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> L >> R;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> m[i][j];
int res = 0;
while (1) {
updated = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!bor[i][j]) {
v.clear();
v.push_back({ i,j });
idxSum = m[i][j];
bfs({ i, j });
}
//열린 국경이 있으면
if (v.size() >= 2) { //한 연합 내의 국가 개수
updated = true;
int val = idxSum / v.size();
for (int i = 0; i < v.size(); i++) {
m[v[i].first][v[i].second] = val;
}
}
}
}
if (updated) res++;
else break;
init();
}
cout << res << '\n';
return 0;
}
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 17143번: 낚시왕 (C++) (0) | 2019.08.04 |
|---|---|
| 백준 16235번: 나무 재테크 (C++) (0) | 2019.07.30 |
| 백준 17281번: 야구 ⚾ (C++) (0) | 2019.07.26 |
| 백준 17144번: 미세먼지 안녕 (C++) (0) | 2019.07.25 |
| 백준 13335번: 트럭 (C++) (0) | 2019.07.25 |