알고리즘/BOJ
16234. 인구 이동
병인
2019. 10. 16. 09:04
https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명
www.acmicpc.net
<JAVA>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static final int dx[] = { 1, -1, 0, 0 };
static final int dy[] = { 0, 0, 1, -1 };
public static void main(String[] args) throws Exception {
class pos {
pos(int x, int y) {
this.x = x;
this.y = y;
}
int x, y;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken(" "));
int L = Integer.parseInt(st.nextToken(" "));
int R = Integer.parseInt(st.nextToken(" "));
int cnt = 0, sum = 0;
int map[][] = new int[N][N];
boolean visit[][] = new boolean[N][N];
List<pos> list = new ArrayList<>();
Queue<pos> q = new LinkedList<>();
for (int i = 0; i < N; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; ++j) {
map[i][j] = Integer.parseInt(st.nextToken(" "));
}
}
boolean isUpdate = true; // 인구 이동 여부 확인
while (isUpdate) {
isUpdate = false;
visit = new boolean[N][N];
// BFS
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
sum = 0;
visit[i][j] = true;
sum += map[i][j];
q.add(new pos(i, j));
list.add(new pos(i, j));
while (!q.isEmpty()) {
pos cur = q.poll();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny]
|| Math.abs(map[nx][ny] - map[cur.x][cur.y]) < L
|| Math.abs(map[nx][ny] - map[cur.x][cur.y]) > R)
continue;
sum += map[nx][ny];
visit[nx][ny] = true;
q.add(new pos(nx, ny));
list.add(new pos(nx, ny));
isUpdate = true;
}
}
sum /= list.size();
for (int k = 0; k < list.size(); ++k) {
map[list.get(k).x][list.get(k).y] = sum;
}
list.clear();
}
}
}
if (isUpdate) {
++cnt;
}
}
System.out.println(cnt);
}
}<C++>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
int map[50][50];
bool visit[50][50];
int N, L, R, cnt, sum;
struct pos
{
int x, y;
};
vector<pos> v;
queue <pos> q;
int main()
{
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
cin >> N >> L >> R;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> map[i][j];
}
}
bool isUpdate = true; // 인구 이동 여부 확인
while (isUpdate)
{
isUpdate = false;
memset(visit, false, sizeof(visit));
// BFS
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (!visit[i][j])
{
sum = 0;
visit[i][j] = true;
sum += map[i][j];
q.push({ i,j });
v.push_back({ i,j });
while (!q.empty())
{
pos cur = q.front(); q.pop();
for (int dir = 0; dir < 4; ++dir)
{
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny] || abs(map[nx][ny] - map[cur.x][cur.y]) < L || abs(map[nx][ny] - map[cur.x][cur.y]) > R)
continue;
sum += map[nx][ny];
visit[nx][ny] = true;
q.push({ nx,ny });
v.push_back({ nx,ny });
isUpdate = true;
}
}
sum /= v.size();
for (int k = 0; k < v.size(); ++k)
{
map[v[k].x][v[k].y] = sum;
}
v.clear();
}
}
}
if (isUpdate)
{
++cnt;
}
}
cout << cnt;
return 0;
}