[Java] 백준 인구 이동

1. 문제 분석

문제를 제대로 이해해보자. 하루단위로 국가마다 연합을 만들고 인구이동을 하는 것이다.

필자는 인구이동이 일어났다면 하루라고 생각해서 시간이 꽤 걸렸다.

 

DFS를 사용했고 연합이 만들어지는 조건을 달성하면 합쳐주고 합칠 국가가 없으면 걸린 날짜를 반환한다.

연합이 만들어지는 조건은 다음과 같다

 

1. 배열의 인덱스 값을 벗어나면 안된다.

2. 이미 방문한 곳은 가면 안된다.

3. L과 R 사이의 수여야만 한다.

 

3번 조건을 위해 절댓값을 활용했다(Math.abs) 

2. 구현

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

class Point {
	int x, y;

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

public class Solution {

	static int[][] map;
	static int N, L, R;
	static boolean visited[][];
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int answer = 0;
	static ArrayList<Point> list = new ArrayList<>();

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

		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) {
			visited = new boolean[N][N];
			boolean flag = false;
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						dfs(j,i);
						//1 이상이란건 연합이 만들어지는 것
						if(list.size() > 1) {
							flag = true;
							calc();
						}
						list.clear();
					}
				}
			}
			
			if(!flag) break;
			else answer++;
		}
		br.close();
		System.out.println(answer);
	}
	
	//인구 이동
	static void calc() {
		int divCount = list.size();
		int sum = 0;
		
		for(Point p : list) {
			sum += map[p.y][p.x];
		}
		sum = sum/divCount;
		
		for(Point p : list) {
			map[p.y][p.x] = sum;
		}
	}
	
	//dfs로 구현
	static void dfs(int x, int y) {
		visited[y][x] = true;
		list.add(new Point(x, y));
		
		for(int i = 0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx < 0 || my < 0 || mx >= N || my >= N)
				continue;
			if (visited[my][mx])
				continue;
			int range = Math.abs(map[my][mx] - map[y][x]);
			if (range < L || range > R)
				continue;
			
			dfs(mx, my);
		}
	}
}

 

하루단위로 구현하기 위해 while문을 사용했다.

만약 연합이 1개라도 안 만들어지면 break를 했고 있다면 calc를 통해 연합마다 인구를 계산했다.

 

BFS로 풀어도 되는 문제지만 DFS로 푸는 것이 메모리나 구현면에서 더 좋았다.

3. 마무리

당연히 인접한 국가? BFS로 풀었는데 메모리초과가 나왔다.

문제도 잘못보고 메모리초과나서 DFS로 바꾸고.. 여러모로 이상한 문제