[BaekJoon] 16234 인구 이동

1.  문제 링크

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

2.  문제

요약

• N x N 크기의 땅이 1 X 1개의 칸으로 나누어져 있는데, 각각의 땅에는 나라가 하나씩 존재하고 r행 c열에 있는 나라에는 A[r][c]명이 살고 있습니다.
• 인접한 나라 사이에는 국경선이 존재합니다.
• 인구 이동은 하루 동안 아래와 같이 진행되고, 더 이상 아래 방법으로 인구 이동이 없을 때까지 진행됩니다.
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 하루 동안 엽니다.
  • 위의 조건으로 열어야하는 모든 국경선이 열렸다면 인구 이동을 시작합니다.
  • 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있다면, 그 나라들을 하루 동안은 연합이라고 합니다.
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 되고 소숫점 아래는 버립니다.
  • 연합을 해체하고, 모든 국경선을 닫습니다.
• 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 50보다 작거나 같은 N과 1보다 크거나 같고 100보다 작거나 같은 L, L보다 크거나 같고 100보다 작거나 같은 R이 주어집니다. 두 번째 줄부터 N개의 줄에는 0보다 크거나 같고 100보다 작거나 같은 각 나라의 인구수가 주어집니다.
• 출력: 첫 번째 줄에 인구 이동이 며칠 동안 발생하는지 출력합니다.

3.  소스코드

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.LinkedList;
import java.util.Queue;

public class Main {
	static int[][] map;
	boolean[][] visited;
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, -1, 0, 1};
	ArrayList<Point> list;
	static int l, r;
	
	public int bfs(int x, int y) {
		Queue<Point> queue = new LinkedList<Point>();
		list = new ArrayList<Point>();
		queue.offer(new Point(x, y));
		list.add(new Point(x, y));
		visited[x][y] = true;
		int total = map[x][y];
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length && !visited[cx][cy]) {
					int difference = Math.abs(map[cur_point.x][cur_point.y] - map[cx][cy]);
					if(l <= difference && difference <= r) {
						queue.offer(new Point(cx, cy));
						list.add(new Point(cx, cy));
						total += map[cx][cy];
						visited[cx][cy] = true;
					}
				}
			}
		}
		return total;
	}
	
	public int getTimes() {
		int count = 0;
		while(true) {
			visited = new boolean[map.length][map[0].length];
			boolean canMove = false;
			for(int i = 0; i < map.length; i++) {
				for(int j = 0; j < map[i].length; j++) {
					if(!visited[i][j]) {
						int total = bfs(i, j);
						if(list.size() > 1) {
							int avg = total / list.size();
							for(Point p : list) {
								map[p.x][p.y] = avg;
							}
							canMove = true;
						}
					}
				}
			}
			if(!canMove) {
				return count;
			}
			count++;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int num = Integer.parseInt(input[0]);
		l = Integer.parseInt(input[1]);
		r = Integer.parseInt(input[2]);
		map = new int[num][num];
		for(int i = 0; i < num; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < num; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getTimes() + "\n");
		bw.flush();
		bw.close();
	}
}

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

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 방문하지 않은 나라들을 방문하면서 BFS 알고리즘을 이용하여 연합에 해당하는 나라들을 구하고 연합인 나라들의 인구수의 합을 구합니다.
• 탐색하고자 하는 나라를 연합인 나라들을 저장하는 list 변수에 저장하고 다른 나라들을 탐색하는데 탐색하고자 하는 나라의 인구수와 다른 나라의 인구수 차이가 L 이상 R 이하인 다른 나라들만 탐색합니다.
• 방문한 나라들을 list 변수에 저장하고 인구수 합을 sum 변수에 계산하여 저장합니다.
• 모든 나라들을 방문한 후에 list의 크기가 1보다 크다면 인구 이동을 합니다.
• 위 과정을 인구 이동이 일어나지 않을 때까지 반복하여 인구 이동이 며칠 동안 발생하는지 구합니다.

1. 주어진 나라들의 인구수를 map이라는 2차원 배열에 담고 인구 이동이 며칠 동안 발생했는지를 나타내는 count 변수를 생성하고 0으로 초기화합니다.
2. 더 이상 인구 이동이 일어나지 않을 때까지 무한 루프를 돌면서 인구 이동이 며칠 동안 발생하는지 구합니다.
   1. BFS 알고리즘을 이용하여 탐색할 때 각 나라를 방문하였는지를 나타내는 2차원 배열 visited를 생성하며 인구 이동이 일어났는지를 나타내는 canMove 변수를 생성하고 false로 초기화합니다.
   2. 각 나라들을 탐색하면서 해당 나라가 아직 방문되지 않았다면 BFS 알고리즘을 통해 해당 나라가 포함된 연합을 구하고 해당 연합의 전체 인구수를 구합니다.

      1. BFS를 수행하기 위한 Queue를 생성하고 연합에 해당하는 나라들을 담기 위한 list라는 ArrayList 변수를 생성합니다.

      2. queue에 탐색하고자 하는 나라를 넣고 list에도 탐색하고자 하는 나라를 넣습니다. 또한 탐색하고자 하는 나라는 방문하였으니 해당 위치의 visited 값을 true로 변경합니다.

      3. 연합의 인구수 합을 나타내는 total 변수를 생성하고 탐색하고자 하는 나라의 인구수로 초기화합니다.

      4. queue가 비워지기 전까지 반복문을 돌면서 연합을 구하고 해당 연합의 인구수 합을 구합니다.

         • queue에서 현재 탐색하고자 하는 나라를 꺼내고 해당 나라를 cur_point라는 변수에 저장합니다.
         • 탐색하고자 하는 나라의 상하좌우 나라를 확인하여 해당 나라가 map 안에 존재하고 아직 방문되지 않았는지 확인하고 그렇다면 탐색하고자 하는 나라와 해당 나라의 인구수 차를 구합니다.
         • 인구수 차가 l 이상, r 이하라면 연합에 포함되기 때문에 해당 나라를 list에 추가하고 해당 나라의 상하좌우 나라를 확인하며 그 나라들도 연합에 포함되는지 확인하기 위해 해당 나라를 queue에 추가합니다.
         • total 변수에 해당 나라의 인구수를 더해주고 해당 나라를 방문하였으니 해당 위치의 visited의 값을 true로 변경합니다.

      5. 4번의 반복문이 끝났을 때의 total 값이 해당 연합의 전체 인구수가 되고 해당 값을 반환합니다.

   3. 만약 연합에 해당하는 나라들을 저장하는 list의 크기가 1을 넘는다면 연합에 한 개의 나라보다 더 많은 나라가 있으므로 인구 이동이 가능하기 때문에 연합에 해당하는 나라들의 인구수 평균을 구하고 연합에 해당하는 나라들의 인구수를 모두 평균값으로 변경합니다.
   4. 인구 이동을 진행하였기 때문에 canMove의 값을 true로 변경합니다.
   5. 만약 canMove의 값이 false라면, 즉 인구 이동이 일어나지 않았다면 인구 이동을 모두 마친 것이므로 인구 이동이 며칠 동안 발생했는지를 나타내는 count 변수의 값을 출력합니다.
   6. 만약 그렇지 않다면 count의 값을 1 증가시키고 반복문을 인구 이동을 마칠 때까지 수행합니다.