문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
시간 제한 : 2초
메모리 제한 : 512MB
연합을 이루기 위해 각 나라들에서 상하좌우로 인접한 나라들과의 인구 차이를 비교할 필요가 있습니다.
이때 특정 나라가 속한 연합을 찾기 위해서 그 나라에서 DFS를 통해 인구 차이가 L명 이상, R명 이하인 나라로 탐색하며 연합을 구했습니다.
연합을 구한 이후 속한 나라들에 연산을 적용하는 방법으로 한 연합에 대한 인구 이동을 끝냈고, 방문하지 않은 모든 나라에 동일한 연산을 적용하였습니다.
연합끼리는 영향을 주지 않기 때문에 원본 map 배열에 바로 값을 업데이트하였습니다.
public static boolean move() {
boolean visit[][] = new boolean[map.length][map[0].length];
isMoved = false;
// 모든 나라에 대해 수행
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if (!visit[i][j]) {
dfs(i, j, visit);
}
}
}
return isMoved;
}
boolean 타입의 visit[][] 배열을 선언하여, 방문하지 않은 모든 나라에 대해 dfs를 시작합니다.
public static boolean dfs(int i, int j, boolean[][] visit) {
Stack<Country> stack = new Stack<>();
List<Country> tmp = new ArrayList<>();
int groupSum = 0;
// 처음 방문하는 나라를 stack에 추가
stack.add(new Country(i, j));
visit[i][j] = true;
while (!stack.isEmpty()) {
Country now = stack.pop();
tmp.add(now);
groupSum += map[now.x][now.y];
for (int m = 0; m < 4; m++) {
int xx = now.x + mx[m];
int yy = now.y + my[m];
if (xx >= 0 && xx < map.length && yy >= 0 && yy < map[0].length && !visit[xx][yy]) {
if (check(map[now.x][now.y], map[xx][yy])) {
visit[xx][yy] = true;
isMoved = true;
stack.add(new Country(xx, yy));
}
}
}
}
if(tmp.size() > 0)
groupSum /= tmp.size();
for (Country c : tmp) map[c.x][c.y] = groupSum;
return isMoved;
}
stack을 사용하여 dfs를 수행하는 부분입니다.
인구 이동이 가능하면서 방문하지 않은 나라를 다음 탐색 나라로 추가합니다. (
이후 인구 이동 발생 여부를 확인하기 위해 isMoved라는 값을 리턴합니다.
public static boolean check(int n1, int n2){
if (n1 < n2) {
int tmp = n1;
n1 = n2;
n2 = tmp;
}
if( ((n1-n2) >= L) && ((n1-n2) <= R) ) return true;
return false;
}
인구 이동이 가능한지 확인하는 메서드입니다.
기본적으로 n1이 더 크다고 가정하였기 때문에 n1이 더 작은 경우 swap을 통해 차를 계산합니다.
https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
'PS > 백준' 카테고리의 다른 글
[ BOJ 2776 ] 암기왕 ( JAVA ) (0) | 2023.07.28 |
---|---|
[ BOJ 1966 ] 프린터 큐 ( JAVA ) (0) | 2023.07.26 |
[ BOJ 4179 ] 불! ( JAVA ) (0) | 2023.05.26 |
[ BOJ 2075 ] N번째 큰 수 ( JAVA ) (1) | 2023.05.16 |
[ BOJ 9205 ] 맥주 마시면서 걸어가기 ( JAVA ) (0) | 2023.04.11 |