BOJ) 인구 이동
인구 이동
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모��
www.acmicpc.net
풀이
인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다.
처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다.
얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다.
grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합하지 않을 때 까지 while으로 반복했다.
코드가 길어서 복잡해보이지만, main은 입력값 저장을 해주는 것이 전부이고, solution이 위에서 말한 로직을 실행한다.
맵을 탐색하면서 group ==0인 경우 (아직 그룹이 정해지지 않은 경우)에 grouping을 해주면서 동시에 nations (나라의 수를) 세주었다.
또한, int형 변수 populations에 인구 수를 저장하면서, 마지막에 HashMap에 넣을 때, populations/nations 로 평균 값을 저장했다.
사진처럼, 메모리와 시간이 좋지 못한 코드다.
더 좋게 바꿀 수 없을지 고민하다가, HashMap에 저장하고 호출하지말고 group의 index를 가진 배열을 생성해서 저장하고 호출하게 바꿨다.
group의 수는 grouping을 하기 전까지 알 수 없지만, 모두 인접한 곳과 인구이동을 할 수 없는 경우 각자 하나씩 group이 되기 때문에 최대 N*N개의 그룹이 생성되는 것을 유추했다.
group의 평균인구를 담을 newPopulations 배열을 생성하고, HashMap에 저장했던 위치에 배열에 저장하도록 했다.
눈에 띄게 확 좋아졌다고는 할 수 없지만, 조금 더 효율적인 코드라고 할 수 있다.
메모리를 적게 쓰고 빠르게 푼 사람들은 어떻게 풀었는지 봤는데, find-union으로 푼 사람이 대부분이었다.grouping하는 자체가 find-union으로 대체 가능하기 때문에, 다음에 풀 기회가 생기면 find-union으로 풀어봐야겠다.
코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
public static void main(String[] args) throws IOException {
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[][] map = new int[N][N];
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());
}
}
solution(N,L,R,map);
br.close();
}
private static void solution(int N, int L, int R, int[][] map) {
int answer =0;
boolean isChange = true;
while(isChange) {
isChange = false;
int[][] group = new int[N][N];
int groupIdx =0;
LinkedList<Pos_16234> moveList = new LinkedList<>();
HashMap<Integer,Integer> populationMap = new HashMap<>();
for(int y=0; y<N; y++) {
for(int x=0; x<N; x++) {
if(group[y][x] ==0) {
group[y][x] = ++groupIdx;
moveList.offer(new Pos_16234(x,y));
int nations =1;
int populations = map[y][x];
while(!moveList.isEmpty()) {
Pos_16234 pos = moveList.poll();
for(int i=0; i<4; i++) {
int nx = pos.x +dx[i];
int ny = pos.y +dy[i];
if(isInArea(nx,ny,N)) {
if(group[ny][nx] ==0 && isUnited(map[pos.y][pos.x], map[ny][nx], L, R)) {
isChange = true;
group[ny][nx] = groupIdx;
nations++;
populations += map[ny][nx];
moveList.offer(new Pos_16234(nx,ny));
}
}
}
}
populationMap.put(groupIdx, populations/nations);
}
}
}
if(isChange) {
answer++;
}
for(int y=0; y<N; y++) {
for(int x=0; x<N; x++) {
map[y][x] = populationMap.get(group[y][x]);
}
}
}
System.out.println(answer);
}
private static boolean isUnited(int val1, int val2, int L, int R) {
return Math.abs(val1-val2) >= L && Math.abs(val1-val2) <=R;
}
private static boolean isInArea(int x, int y, int max) {
return x>=0 && x<max && y>=0 && y<max;
}
}
class Pos_16234 {
int x;
int y;
public Pos_16234(int x, int y) {
this.x= x;
this.y = y;
}
}
코드 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
public static void main(String[] args) throws IOException {
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[][] map = new int[N][N];
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());
}
}
solution(N,L,R,map);
br.close();
}
private static void solution(int N, int L, int R, int[][] map) {
int answer =0;
boolean isChange = true;
while(isChange) {
isChange = false;
int[][] group = new int[N][N];
int groupIdx =0;
LinkedList<Pos_16234> moveList = new LinkedList<>();
int[] newPopulations = new int[N*N+1];
for(int y=0; y<N; y++) {
for(int x=0; x<N; x++) {
if(group[y][x] ==0) {
group[y][x] = ++groupIdx;
moveList.offer(new Pos_16234(x,y));
int nations =1;
int populations = map[y][x];
while(!moveList.isEmpty()) {
Pos_16234 pos = moveList.poll();
for(int i=0; i<4; i++) {
int nx = pos.x +dx[i];
int ny = pos.y +dy[i];
if(isInArea(nx,ny,N)) {
if(group[ny][nx] ==0 && isUnited(map[pos.y][pos.x], map[ny][nx], L, R)) {
isChange = true;
group[ny][nx] = groupIdx;
nations++;
populations += map[ny][nx];
moveList.offer(new Pos_16234(nx,ny));
}
}
}
}
newPopulations[groupIdx] = populations/nations;
}
}
}
if(isChange) {
answer++;
}
for(int y=0; y<N; y++) {
for(int x=0; x<N; x++) {
map[y][x] = newPopulations[group[y][x]];
}
}
}
System.out.println(answer);
}
private static boolean isUnited(int val1, int val2, int L, int R) {
return Math.abs(val1-val2) >= L && Math.abs(val1-val2) <=R;
}
private static boolean isInArea(int x, int y, int max) {
return x>=0 && x<max && y>=0 && y<max;
}
}
class Pos_16234 {
int x;
int y;
public Pos_16234(int x, int y) {
this.x= x;
this.y = y;
}
}