[알고리즘] 인구 이동 (백준 16234번)

16234번: 인구 이동

 삼성 기출 문제이다. 예전에 한 번 풀어본 적이 있는 문제이고 시뮬레이션 + 그래프 탐색 문제다. BFS 혹은 DFS 탐색을 하되 몇 번 탐색하느냐를 출력해야한다.

 

Solution

 로직 자체는 어려울 것이 없다. 인구 이동이 최대 2000번 이하라고 했으니 2000번까지만 반복문을 돌리고 그 안에서 BFS 혹은 DFS로 탐색을 하는데 이 때 한 번의 탐색동안 연결되는 덩어리가 한 연합이 된다.

 그렇게 (0, 0) ~ (N - 1, N - 1) 까지 탐색을 완료해서 한 번이라도 이동이 있었으면 인구이동의 횟수는 증가한다.

 

 문제를 풀다가 특이한 점을 발견했는데 과거에 풀었던 코드에선 400ms 대로 통과가 되었는데 이번엔 600ms 밑으로 내려가지 않는다. 예전 코드는 DFS를 썼고 이번 코드는 BFS를 썼다는 차이점 밖에 없는데 원인이 뭔지 모르겠다. BFS인지 DFS인지에 따라서도 속도차이가 나는 것일까

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int map[][];
	static boolean visited[][];
	static int N, L, R;

	public static void solution() throws Exception
	{
		StringTokenizer strtok = new StringTokenizer(br.readLine());
		N = Integer.parseInt(strtok.nextToken());
		L = Integer.parseInt(strtok.nextToken());
		R = Integer.parseInt(strtok.nextToken());

		map = new int[N][N];

		for(int i = 0;i < N;i++)
		{
			strtok = new StringTokenizer(br.readLine());
			for(int j = 0;j < N;j++)
				map[i][j] = Integer.parseInt(strtok.nextToken());
		}

		Queue<Country> queue = new LinkedList<>();
		ArrayList<Country> countries = new ArrayList<>();
		int x[] = {-1, 1, 0, 0};
		int y[] = {0, 0, -1, 1};

		for(int move_count = 0; move_count <= 2000 ;move_count++)
		{
			visited = new boolean[N][N];
			boolean isMoved = false;

			for(int i = 0;i < N;i++)
			{
				for(int j = 0;j < N;j++)
				{
					if(!visited[i][j])
					{
						int sum = map[i][j];

						queue.offer(new Country(i, j));
						countries.add(queue.peek());

						visited[i][j] = true;

						while(!queue.isEmpty())
						{
							Country now = queue.poll();

							for(int n = 0;n < 4;n++)
							{
								int next_x = now.x + x[n];
								int next_y = now.y + y[n];

								if(0 <= next_x && next_x < N && 0 <= next_y && next_y < N)
								{
									//차이
									int subtract = Math.abs(map[now.x][now.y] - map[next_x][next_y]);

									if(!visited[next_x][next_y] && L <= subtract && subtract <= R)
									{
										sum += map[next_x][next_y];

										Country next = new Country(next_x, next_y);
										countries.add(next);
										queue.offer(next);
										visited[next_x][next_y] = true;
									}
								}
							}

						}

						//2개 이상 연결되었다면 인구 이동이 있었다는 것
						if(countries.size() > 1)
						{
							isMoved = true;
							int average = sum / countries.size();

							for(Country c : countries)
								map[c.x][c.y] = average;
						}
						countries.clear();
					}
				}
			}

			//이동이 없었으면 이동 횟수 출력 후 종료
			if(!isMoved)
			{
				bw.write(move_count+"");
				break;
			}
		}

	}

	static class Country{
		int x, y;

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




	public static void main(String[] args) {
		try
		{
			solution();

			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}