백준 16234 : 인구 이동

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

16234번: 인구 이동

[ 문제풀이 ]

이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 골드 5의 난이도답게 정말 간단한 문제이다.

dfs를 통해 경계선을 공유한 영역들을 나눠주기만 한다면 쉽게 해결할 수 있을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N, L, R, answer, check, count;
	static int[][] A, visit;
	static boolean mark;
	static List<Integer> list;

	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		A = new int[N][N];
		visit = new int[N][N];
		list = new ArrayList<>();
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; ++j) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		do {
			//변수들 초기화
			init();
			//경계선을 open
			openBoundary();
			//각 경계선에 속하는 인구 이동
			movePeople();
			//인구 이동이 발생했다면
			if (mark) answer++;
		} while(mark);

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void init() {
		mark = false;
		check = 1;
		list.clear();
		for (int i = 0; i < N; ++i) {
			Arrays.fill(visit[i], 0);
		}
	}

	public static void openBoundary() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (visit[i][j] != 0) continue;
				//방문하지 않은 영역을 dfs를 돌려 국경선을 열 수 있는 영역을 체크 후
				//(방문한 영역의 인구 총합 / 방문한 영역의 개수)를 리스트에 넣어줌
				list.add(dfs(i, j) / count);
				check++;
				count = 0;
			}
		}
	}

	public static int dfs(int y, int x) {
		int sum = A[y][x];
		count++;
		visit[y][x] = check;

		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (visit[ny][nx] != 0) continue;

			int diff = Math.abs(A[y][x] - A[ny][nx]);
			//인접한 영역의 인구 수 차이가 L이상 R이하라면 dfs를 돌려 방문 체크해줌
			if (diff >= L && diff <= R) {
				sum += dfs(ny, nx);
				mark = true;
			}
		}
		return sum;
	}

	public static void movePeople() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (visit[i][j] == 0) continue;
				//방문한 영역이라면 인구를 분배
				A[i][j] = list.get(visit[i][j] - 1);
			}
		}
	}
}