BOJ - 16234 인구이동

16234 인구이동 : https://www.acmicpc.net/problem/16234

Problems

---

Solves

1. 인구 이동이 없을때 까지 반복문
2. BFS를 통해 연합을 구하는 함수 makeGroup
3. makeGroup에서 반환한 해당 연합의 좌표 리스트로 인구 이동 결과를 갱신하는 함수 setMove
   이 프로세스로 구현했다.

인구 이동의 여부는 이번 턴에 연합을 구했을때 makeGroup에서 반환된 연합의 좌표 리스트가 없는 경우를 통해 구현했다. 인구 이동의 일수는 최대 2000번 무조건 발생한다는 조건이 있었기에 가능했다.

makeGroup은 BFS를 통해 해당 좌표에서 상하좌우의 나라의 인구 차이가 L이상 R이하인 나라를 찾아 방문여부를 표시 해줄 visit배열과 연합표시를 해줄 groupMap 배열을 통해 조건을 만족하는 나라의 좌표를 List로 묶어 반환해주었다.
이 때 조심해야할 점은 시작 좌표인 x,y좌표를 List에 넣어주는 코드의 위치이다.
인접한 나라와의 인구 차이가 조건을 만족했을 때 시작 좌표를 넣어줬는데 flag를 통해 시작 좌표를 List에 저장여부를 확인하고 저장해주었다.

makeGroup에서 연합 좌표 리스트를 반환했을 때 리스트에 연합 좌표가 존재한다면 각 연합별 좌표들을 저장하는 pointLists에 저장해준다.
그래서 만약 연합이 생성되지 않았다면 인구 이동 반복문을 종료해준다.

setMove는 makeGroup에서 반환해준 연합 좌표 리스트가 유효할때 연합 좌표들의 인구의 합을 갱신해준다.

모든 과정을 마쳤다면 인구 이동 일 수인 res를 카운트 해준다.

---

Code

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

public class 인구이동 {
	static int N;
	static int L;
	static int R;
	static int[][] map;
	static int[][] groupMap;
	static boolean[][] visit;
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 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(), " ");
		int res = 0;

		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());
			}
		}

		//인구 이동이 없을때 까지 반복
		while (true) {
			int group = 1;
            //각 나라별 연합 표시
			groupMap = new int[N][N];
            //각 나라별 방문 여부
			visit = new boolean[N][N];
            //연합별 좌표 리스트
            //pointLists의 index가 연합 리스트
			List<List<Point>> pointLists = new ArrayList<>();
            //연합은 1부터 구분하므로 0은 빈 리스트
			pointLists.add(new ArrayList<>());
			for (int i = 0; i < N * N; i++) {
				if (!visit[i / N][i % N]) {
					List<Point> groupList = makeGroup(i % N, i / N, group);
                    //makeGroup에서 연합 좌표 리스트가 유효하다면 group구분 +1, 그리고 pointsLists에 연합의 좌표 리스트를 넣어주어 while문 break 통과
					if (groupList.size() > 0) {
						group++;
						pointLists.add(groupList);
					}
				}
			}
			if (pointLists.size() == 1)
				break;

			//인구 이동이 발생하는 연합의 인구 수 갱신
			for (int g = 1; g < pointLists.size(); g++) {
				setMove(pointLists.get(g));
			}
			res++;
		}
		bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
	}

	//연합의 인구 수 갱신
	static void setMove(List<Point> groupList){
		int sum = 0;
		for(Point p : groupList){
			sum += map[p.y][p.x];
		}
		for(Point p : groupList){
			map[p.y][p.x] = sum/groupList.size();
		}
	}

	//연합 생성
	static List<Point> makeGroup(int x, int y, int groupNumber) {
		List<Point> pointList = new ArrayList<>();
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(x, y));
		visit[y][x] = true;
		boolean flag = false;
		while (!queue.isEmpty()) {
			Point p = queue.poll();

			for (int i = 0; i < 4; i++) {
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
				if (ny >= 0 && nx >= 0 && ny < N && nx < N && !visit[ny][nx]) {
					int gap = Math.abs(map[p.y][p.x] - map[ny][nx]);
                    //인접한 나라와의 인구 수 조건
					if (gap >= L && gap <= R) {
                    	//인구 수 차이 조건까지 만족했다면 시작 좌표를 연합 좌표 리스트에 저장
						if (p.y == y && p.x == x && !flag) {
                        	//한 번만 연합 좌표 리스트에 시작 좌표를 넣기위함
							flag = true;
							pointList.add(new Point(x, y));
							groupMap[p.y][p.x] = groupNumber;
						}

						visit[ny][nx] = true;
						groupMap[ny][nx] = groupNumber;
						queue.offer(new Point(nx, ny));
						pointList.add(new Point(nx, ny));
					}
				}
			}
		}
		return pointList;
	}

	static class Point {
		int x;
		int y;

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

---

Result

나름 쉽게 풀었지만 몇몇의 조건들을 놓침으로써 한시간 반 정도 걸렸다. 시간을 좀 더 단축하기 위해 더.. 노력하자