[백준] 16234번: 인구 이동 문제 풀이

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

접근 방식

dfs를 통해 연합이 가능한 곳까지 방문처리를 하며 탐색한다.
배열의 모든 요소를 검사하며 방문하지 않은 곳마다 갯수를 세며 dfs를 진행한다.
만약 하루에 방문한 횟수가 N*N이라면, 연합의 갯수가 0, 즉 더 이상 주변 마을과 연합을 맺을 수 없는 상태를 의미한다.

연합 가능한 마을 탐색

dfs를 진행하면서 다른 마을을 방문할 때 마다 하나의 연합에 몇개의 마을이 속해있는지 union으로 증가시켜준다.
또한 해당 연합의 전체 인구수를 함께 구해준다.
방문하고자 하는 마을과 현재 마을의 인구수 차이가 L과 R 사이라면 방문하여 연합한다.

static void dfs(int y, int x, int num) {
	union++;
	popSum += arr[y][x];
	v[y][x] = num;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0<=ny&&ny<N&&0<=nx&&nx<N&&v[ny][nx] < num) {
			int gap = Math.abs(arr[y][x]-arr[ny][nx]);
			if (L<=gap&&gap<=R) dfs(ny,nx,num);
		}
	}
}

인구 이동

전체 마을을 돌면서 해당 마을에 대한 연합의 수와 연합 전체 인구수 정보를 가져온다.
가져온 정보를 토대로 해당 마을의 인구수를 조정한다.

static void move() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int [] data = un.get(v[i][j]-1);
			arr[i][j] = data[1]/data[0]; // 해당 연합의 전체 인구수 / 해당 연합의 마을 수
		}
	}
}

반복

각 마을을 방문하여 몇번 연합인지 표시한다. 방문이 끝났으면 연합의 번호 num을 증가시킨다.
(인구 이동 시 각 마을의 연합 번호를 통해 연합의 정보를 불러온다.)
방문 가능한 마을을 탐색하며 구한 union(해당 연합의 마을 수)와 popSum(해당 연합의 전체 인구 수)를 배열로 담아 연합들의 정보를 담을 리스트에 넣어준다.

만약 생성된 연합의 수(num)이 N*N가 되면 아무도 연합을 한 마을이 없다는 의미가 되므로 break;
그렇지 않다면 인구 이동을 시작하며, 날짜를 카운트해준다.

회고

문제의 예제는 다 맞았는데 계속해서 틀린 답이 나왔다. 혹시나 하고 반복문의 종료 조건을 다시 세워보니 정답이 되었다. 이번에도 한번에 완벽하게 문제를 풀지 못한 것 같다.

전체 코드

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

public class Main {
	static int N, L, R, union, popSum;
	static int [][] arr, v;
	static boolean [][] moved;
	static int [] dy = {-1, 1, 0, 0};
	static int [] dx = {0, 0, -1, 1};
	static ArrayList<int []> un;
    
	static void dfs(int y, int x, int num) {
		union++;
		popSum += arr[y][x];
		v[y][x] = num;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0<=ny&&ny<N&&0<=nx&&nx<N&&v[ny][nx]<num) {
				int gap = Math.abs(arr[y][x]-arr[ny][nx]);
				if (L<=gap&&gap<=R) dfs(ny,nx,num);
			}
		}
	}
    
	static void move() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int [] data = un.get(v[i][j]-1);
				arr[i][j] = data[1]/data[0];
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		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());
		arr = new int[N][N];
        
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) arr[i][j] = Integer.parseInt(st.nextToken());
		}
        
		int cnt = 0;
		while (true) {
			int num = 1;
			v = new int[N][N];
			un = new ArrayList<>();
			moved = new boolean[N][N];
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (v[i][j]==0) {
						union = 0;
						popSum = 0;
						dfs(i,j,num++);
						un.add(new int[] {union, popSum});
					}
				}
			}
			if (num - 1 == N*N) break;
			move();
			cnt++;
		}
        
		System.out.println(cnt);
	}
}