[백준 - Java] 16234번 : 인구 이동

문제

www.acmicpc.net/problem/16234

16234번: 인구 이동

설명

문제의 설명이 부족한 것 같다.

처음에 나는 인구 이동을 할 때마다 정답 변수 answer를 +1 해주어 총인구 이동 수를 구했다.

 

하지만 인구 이동 할때마다 +1 해주는 것이 아니라, 인구 이동이 총 며칠 동안 이루어졌는지를 구해야 한다.

 

즉, 전체 정점(나라)을 돌면서 연합이 이루어지고, 인구가 이동하는 작업을 따져본다면 인구 이동은 0~n번 일어날 수 있다.

 

예를 들어 입력 5번의 경우

 

// 예제 5번 입력 
4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

// 예제 5번 출력 
0일차
인구 이동
10 100 50 50 
50 50 50 50 
50 50 50 50 
50 50 100 50 

1일차
인구 이동
30 100 50 50 
30 50 50 50 
50 50 50 50 
50 50 100 50 

인구 이동
30 66 66 50 
30 66 50 50 
50 50 50 50 
50 50 100 50 

인구 이동
30 66 66 50 
30 66 50 50 
50 50 62 50 
50 62 62 62 

2일차
인구 이동
48 48 66 50 
30 66 50 50 
50 50 62 50 
50 62 62 62 

인구 이동
48 48 54 54 
54 54 54 50 
54 54 54 54 
54 54 62 54 

3일차
3

 

총인구 이동의 횟수는 6이지만 하루에 인구 이동이 있었느냐에 따라 정답은 3을 출력해야 한다.

 

그렇기에 처음에 내가 생각했던 것처럼 인구 이동을 할 때마다 +1을 해주는 것이 아니라,

전체 정점을 도는 것을 하루로 생각하고, 하루에 인구 이동이 0번이든 n번이든 1번 이상 일어났다면 answer를 +1 해주어야 한다.

 

이를 유념해 코드를 짜면 된다.

각 정점을 모두 순회하는 것을 하루로 두고, 이 하루 동안 연합 후 인구 이동을 한 번이라도 안 했으면 정답을 출력하며 끝낸다.

 

순회하며 각 정점을 기준으로 BFS 탐색을 진행한다. (visited [x][y] 값이 true로 이미 연합이 되었던 나라는 제외)

인접한 정점과의 차이가 L 이상 R이하가 된다면 해당 인접 정점을 UnionList에 넣어 연합하는 나라로 분류한다.

BFS 탐색이 끝나고 UnionList의 사이즈가 1보다 크다는 것은 연합하는 나라가 있다는 것으로, 이를 바탕으로 인구 이동을 한다.

 

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int N, L, R;
	public static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();

		map = new int[N][N];

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		while(true) {	
			boolean isBfs = false;

			visited = new boolean[N][N];
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(!visited[i][j]) { // 이미 연합을 이루었던 경우는 pass 

						if(bfs(i, j))
							isBfs = true;
					}

				}
			}

			if(!isBfs) {
				// 전체 정점을 다 돌면서, 인구 이동이 한번이라도 안 일어나 isBfs가 false라면 break;
				break;
			} else {
				// 전체 정점을 도는 것을 하루로 생각한다면, 하루에 각 정점들에서 총 n번의 인구 이동이 일어날 수 있다. 
				// 인구 이동을 할 때마다 answer를 +1 하는 것이 아니라, 하루에 인구 이동이 n번이든 뭐든 1번 이상 일어난다면 +1을 해줘야 함. 
				answer++;
			}
		}

		System.out.println(answer);
	}

	public static void print(int[][] map) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	// BFS를 이용해 국경선을 공유하면서, 인구 차이도 만족하는 나라를 찾음 
	public static boolean bfs(int x, int y) {
		boolean isUnion = false; // 인구 이동이 한번도 일어나지 않는다면 false 반환 
		
		ArrayList<Point> unionList = new ArrayList<>(); // 연합에 속하는 나라의 좌표 리스트 
		unionList.add(new Point(x, y));
		int count = 1; // 연합을 이루고 있는 나라의 개수 (처음엔 (x, y) 넣으니 1부터 시작  
		int sum = map[x][y];

		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(x, y));
		visited[x][y] = true;

		while(!queue.isEmpty()) {
			int curX = queue.peek().x;
			int curY = queue.poll().y;

			for(int i = 0; i < 4; i++) { // 상좌하우 검사 
				int nx = curX + dx[i];
				int ny = curY + dy[i];

				if(nx < 0 || ny < 0 || nx >= N || ny >= N) // 범위 벗어나면 pass 
					continue;

				if(visited[nx][ny]) // 이미 확인한 곳이라면 pass 
					continue;

				// 두 나라의 인구 차이가 L명 이상, R명 이하라면 연합 가능 
				int val = Math.abs(map[curX][curY] - map[nx][ny]);

				if(val >= L && val <= R && !visited[nx][ny]) {
					unionList.add(new Point(nx, ny));
					count++;
					sum += map[nx][ny];
					
					visited[nx][ny] = true;
					queue.add(new Point(nx, ny));
				}
			}
		}
		
		if(unionList.size() > 1) { // (x, y) 좌표를 기준으로 연합이 이루어진 경우 
			isUnion = true; // 인구 이동이 일어난 경우 true 반환 
			int result = sum / count;
			
			for(int i = 0; i < unionList.size(); i++) { // 연합 인구수 업데이트 
				Point p = unionList.get(i);
				map[p.x][p.y] = result;
			}
		}
		
		return isUnion;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2316234/src/Main.java

KwonMinha/BOJ