[JAVA] 백준 16234 인구이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

1. 서론

 

어렵지 않은 문제를 어렵고 풀고 n번의 경량화를 거쳐 남들과 비슷하게 풀었다^^ 이러면서 배우는 거겠지 ㅎㅎ

시뮬 + dfs(bfs) 문제이다.

 

2. 문제 풀이

 

맵에 각 좌표에 인구수가 주어진다. 한 좌표를 기준으로 동서남북의 좌표를 봤을 때 현재 위치 좌표와 이웃한 좌표의 차가 L~R 사이이면 이동할 수 있고, 아니면 이동할 수 없다. 이동할 수 있는 것을 기준으로 연합을 나누고 그 연합의 인구수 / 연합을 이루고 있는 칸의 수로 계산한 값이 한 연합의 모든 좌표의 인구수가 된다. 이 루틴을 하루라고 했을 때 며칠 후에 인구이동이 멈추는 지를 구하는 문제이다.

 

내가 어려웠던 점은 연합이 여러 개인지 아닌지 명확하게 적혀있지 않았다는 점이다. (물론 당연히 여러 개이다.)
그리고 동서남북으로 갈 수 있나 없나를 매번 알고 있어줘야 한다고 생각해서 엄청 코드가 복잡해졌었고, 연합을 한 바퀴 돌 때마다 값을 적어주려고 해서 시간이 엄청 오래 걸렸었다. 그래서 이 모든 걸 다 뜯어고쳐서 가벼운 코드를 완성했다.

 

풀이 방식은 다음과 같다.

 

1. 맵 전체를 반복문으로 방문하지 않은 곳을 탐색한다.

2. dfs로 L~R사이라면 동서남북으로 이동하고 아니면 하지 않아서 한 개의 연합을 만들어준다.

3. dfs를 돌면서 저장한 연합의 인구수와 연합을 이루고 있는 칸의 수를 이용해 그 값을 연합별로 저장해둔다.

4. 모든 맵의 연합 처리가 끝나면 연합별로 저장해 둔 값을 전체 맵에 뿌린다.

5. 이전 연합의 맵과 이번 연합의 맵이 같으면 더 이상 이동이 불가하는 것이므로 반복문을 멈추고 아닌 경우 1~4를 반복하고 다시 체크해준다.

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n, l, r, uc, up, ut;
	static int[][] map, union, tmp, utmp;
	static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0}; //동서남북
	static boolean[][] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		
		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());
		}
		
		int cnt = 0;
		union = new int[n][n]; //각 좌표마다 속한 연합의 번호를 저장
		utmp = new int[n][n]; //연합의 변화 감지를 위한 배열
		int[] calc = new int[n * n]; //인구 계산값을 저장하는 배열, idx가 배열의 번호
		while (true) {
			uc = 0; //연합의 수
			visit = new boolean[n][n]; //방문체크
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (!visit[i][j]) {
						up = 0; ut = 0;
						dfs(i, j); //연합 파악
						calc[uc++] = up/ut; //새로 생긴 연합의 계산 값을 적어줌
					}
				}
			}
			
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					map[i][j] = calc[union[i][j]];
			
			if (one()) break; // 더 이동이 불가하다면 멈춤
			copy(utmp, union);
			cnt++;
		}
		
		System.out.println(cnt - 1);
	}
	
	public static boolean one() { //더 이동할 수 있는지 없는지 체크
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (utmp[i][j] != union[i][j]) //이동할 수 없다면 전과 값이 같음
					return false;
		return true;
	}
	
	public static void dfs(int x, int y) {
		if (visit[x][y]) return;
		visit[x][y] = true;
		up += map[x][y]; //연합의 인구수
		union[x][y] = uc; //이 좌표가 어떤 연합에 속하는지 적기
		ut++; //연합을 이루고 있는 칸의 개수
		
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (range(nx, ny) && check(map[x][y], map[nx][ny])) //이동가능 하다면
				dfs(nx, ny);
		}
	}
	
	public static boolean check(int x, int y) { //국경이 열리는지 아닌지 판별
		int tmp = Math.abs(x - y);
		if (tmp >= l && tmp <= r) return true;
		return false;
	}
	
	public static boolean range(int nx, int ny) {
		if (nx >= 0 && nx < n && ny >= 0 && ny < n) return true;
		return false;
	}
	
	public static void copy (int[][] a, int[][] b) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = b[i][j];
	}
}

 

원래는 dfs문 밑에서 새로 생긴 연합 계산 값을 저장하는 게 아니라 매번 채워주려고 해서 시간이 10배가 더 걸렸다.

그래서 번거롭지만 따로 1차원 배열에 적어주고 반복문을 빼줬더니 시간이 10배 빨라졌다 ㅎ

인구이동을 할 수 있는지 없는지 판단하기 위해서는 한 바퀴를 더 돌아서 연합 간의 변동이 있는지 없는지 체크해야 하기 때문에 cnt - 1을 해줬다.(하루 더 cnt 하므로)