백준 16234번 : 인구 이동

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

16234번: 인구 이동

 

 

 

 

 

문제

• 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하기
• 인구 이동은 하루 동안 다음과 같이 진행, 인구 이동이 없을 때까지 지속
  • 국경선을 공유하는 인접한 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
  • 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
  • 연합을 해체하고, 모든 국경선을 닫는다.

 

 

 

 

 

풀이

 인구 이동이 인접한 나라 간 이루어지고, 서로 이동할 수 있는 나라들이 연합을 이루므로 그래프 탐색 유형의 문제이고, 인구 이동이 없을 때까지 구할 때까지 반복해야 하므로 시뮬레이션 유형의 문제이다.

 

 

 

• 시뮬레이션

 while문을 활용해 계속 반복해준다. 인구 이동이 발생했는지를 표시하는 moved라는 boolean형의 변수를 놓고, 인구 이동을 구현하면서 결과에 따라 상태를 변화시킨다. 인구 이동이 끝났을 때, moved가 false면(인구 이동이 없었으면) while문을 종료시키고, 아니면 날짜를 증가시킨다.

int day = 0;
while(true) {
	boolean moved = false; //인구 이동 있는지
	
    //인구 이동(구현해야 함)
			
	if(!moved) break; //인구이동 없었으면 중단
			
	day++;
}

 

 

 

• BFS 탐색 : 연합국 구하기

 국경선이 열리는 인접한 나라들끼리 연합을 형성하므로, 그래프 탐색 중 하나인 BFS(너비우선탐색)으로 같은 연합 찾도록 했다. 그래프의 모든 좌표에 대해 방문하지 않았다면, 그 좌표를 시작으로 BFS를 돌린다. BFS 안에서는 큐를 활용해서 사방탐색을 한다. 그리고 내부에서 합을 계산해준다.

 

 

(while문 안에)

visited = new boolean[N][N];
			
for(int i = 0; i < N; i++) {
	for(int j = 0; j < N; j++) {
		if(!visited[i][j]) bfs(i, j);
	}
}

 

 

 

• 연합 내 인구 이동

연합 내 인구 이동을 위해서는 어떤 좌표에 있는 나라가 인구 이동을 하는지와 연합 내 총 인구수를 알아야 한다.

 

 

• 방법 1 : boolean[][]로 체크

 처음 생각난 방법은 BFS 내부에 따로 boolean형의 2차원 배열을 두어, 탐색하면서 큐에 넣게 되는 좌표들을 true로 표시하는 것이다. BFS 탐색이 끝나고 나면 같은 연합인 국가들이 표시가 될 것이고, for문을 돌려 모든 좌표에 대해 탐색해 true인 국가에 대해 계산한 새로운 인구수로 바꿔줬다.

 

 

그러나, 채점을 돌리면 80%에서 시간 초과가 난다!

 

 게시판을 보니 나처럼 80%에서 시간 초과가 난 사람들이 꽤 있었고, 원인을 알아보니 시간복잡도가 O(day * N^4)으로, N이 최대 50이고 인구 이동이 최대 2000번이 일어날 수 있다고 하니, 최악의 경우 2000*50^4 = 125억이다..

 

 

 

• 방법 2 : ArrayList에 담기

 boolean형의 2차원 배열을 탐색하는 데, N^2의 시간이 걸리므로 이 방법을 바꿔야 한다. ArrayList를 활용해 탐색한 국가의 좌표를 넣어주면 된다. 그리고 BFS 탐색이 끝나고, 리스트에 담긴 모든 좌표에 대해 계산된 새로운 인구수로 바꿔주면 된다. 

 

 

 

 

 

코드

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

public class Main {
	static int N, L, R;
	static int[][] graph;
	static boolean[][] visited;
	
	static List<int[]> list;
	static int sum;
	
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		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());
		
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j = 0; j < N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//구현
		int day = 0; //정답 : 며칠동안 인구이동 발생
		while(true) {
			visited = new boolean[N][N]; //bfs 탐색을 위한 방문체크
			
			boolean moved = false; //인구 이동 있는지
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						list = new ArrayList<>(); //연합
						sum = 0; //연합국 인구 합
						
						bfs(i, j);
						
						//인구 이동
						if(list.size() >= 2) {
							int population = sum / list.size(); //연합국 새 인구수
							
							for(int[] point : list) {
								graph[point[0]][point[1]] = population;
							}
							
							moved = true;
						} 
					}
				}
			}
			
			if(!moved) break; //인구이동 없었으면 중단
			
			day++;
		}
		
		//출력
		System.out.println(day);
	}
	
	public static void bfs(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		
		queue.add(new int[] {i, j});
		visited[i][j] = true;
		list.add(new int[] {i,j});
		
		sum += graph[i][j];
		
		while(!queue.isEmpty()) {
			int x = queue.peek()[0];
			int y = queue.poll()[1];
			
			for(int d = 0; d < 4; d++) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= N) continue; //범위 벗어남
				if(visited[nx][ny]) continue; //이미 방문함
				
				//조건 탐색
				int diff = Math.abs(graph[x][y] - graph[nx][ny]);
				
				if(L <= diff && diff <= R ) { //국경선 열기 가능
					queue.add(new int[] {nx, ny});
					visited[nx][ny] = true;
					list.add(new int[] {nx,ny});
					
					sum += graph[nx][ny];
				}
			}
		}
	}

}

 

 

 

 

결과

 

 

 

 

 

배운점

• n^2 bfs 내, n^2가 들어가지 않게 조심하자
  • 2차원 배열의 체크대신 list에 담자