[백준 16234]인구이동(java)

문제 보러 가기

16234번: 인구 이동

음... 문제가 어려웠던 건 아니겠지... 나는 어려웠다. 우선 이문제는 dfs도 bfs도 가능하다! 다른 분들의 풀이를 보니 어떤 분은 dfs와 bfs를 함께 사용하기도 했다. 나는 bfs를 사용했다

 

고려사항

-인구이동의 조건 : 각 인접한 나라가  L <인구수 <R의 조건을 만족할 때 이동이 가능하다.

 

- 한 번만 하는 게 아닌 국경이 열렸다 닫혀서 map에 인구이동으로 인해 인구수가 바뀌었을 때에도 조건에 충족하는지를 확인해야 한다.

 

-몇 번 이동하는가를 구했을 때 단순히 move() 함수가 불릴 때 mcnt++이면 되겠다고 생각했지만, 한 번에 두영 역에서 인구이동이 일어나게 되면 mcnt+=2가 되기 때문에 몇 회 이동을 하는가를 따졌어야 했다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Ex_16234 {

	static int n;
	static int[][] map;
	static int[][] copy; //같은 영역을 묶기위한 배열
	static boolean[][] visited;
	static int l;
	static int r;
	static int union = 0;

	static boolean flag = false;

	public static void main(String[] armaps) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		l = Integer.parseInt(str[1]);
		r = Integer.parseInt(str[2]);

		map = new int[n][n];
		visited = new boolean[n][n];
		copy = new int[n][n];
		int mcnt = 0; // 총 인구이동이 일어난횟수
        
		for (int i = 0; i < n; i++) {
			str = br.readLine().split(" ");
			for (int j = 0; j < str.length; j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}
        
		while (true) {

//더이상 인구이동이 일어날 수 없는경우 반복문을 빠져나옴
			if (flag)
				break;
			flag = true;
            
//방문하지 않은 국가에대해 탐색
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (visited[i][j] != true) {
						bfs(new Country(i, j));
					}

				}
			}
			mcnt++;
//한번 인구이동이 일어난 후 visited배열 초기화
			for (int i = 0; i < n; i++) {
					Arrays.fill(visited[i], false);
			}
		}
//마지막에 인구이동이 일어나지 않았음에도 mcnt++이 되었으므로 -1해준다
		System.out.println(mcnt-1);

	}
//인구이동을 하는 함수 map에 변경된 인구를 갱신
	public static void move(int sum, int cnt) {

		//인구이동이 일어났으므로 한회차 더 탐색을 진행할 수 있게 flag를 바꿔줌
		flag = false;
		int avg = sum / cnt;
        
        
		for (int i = 0; i < copy.length; i++) {
			for (int j = 0; j < copy[0].length; j++) {
				if (copy[i][j] == union) {
					map[i][j] = avg;
				}
			}
		}

	}
//인구이동이 가능한 영역끼리 묶음.
	public static void bfs(Country c) {
		int[] dx = { 0, 1, 0, -1 };
		int[] dy = { 1, 0, -1, 0 };
		int sum = 0;
		int cnt = 0;
		union++;
		Queue<Country> q = new LinkedList<>();
        
		q.add(c);
		sum += map[c.x][c.y];
		cnt++; 

		while (!q.isEmpty()) {

			Country tmp = q.poll();
			visited[tmp.x][tmp.y] = true;
			copy[tmp.x][tmp.y] = union;

			for (int i = 0; i < 4; i++) {
				int sx = tmp.x + dx[i];
				int sy = tmp.y + dy[i];

				if (sx < 0 || sx >= n || sy < 0 || sy >= n) {
					continue;
				}
				int diff = Math.abs(map[tmp.x][tmp.y] - map[sx][sy]);
				if ((diff < l || diff > r) || visited[sx][sy] == true) {
					continue;
				}
                //조건에 만족할 경우
				q.add(new Country(sx, sy));
				visited[sx][sy] = true;
				copy[sx][sy] = union;
				sum += map[sx][sy];
				cnt++;
			}

		}
        //열린국경선이 없을경우
		if (cnt == 1)
			return;
        //열린국경선이 있어서 인구이동이 가능할 경우
		move(sum, cnt);
		return;

	}

}

class Country {
	int x;
	int y;
	int cnt;

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

	}
}

 

 

 

 

 

bfs를 사용해야겠다 영역을 나눠야겠다를 생각하고 하다 보니 안 되는 부분이 많았다 ;;;;

bfs가 한 번만 돌면 안 되었고 인구이동이 일어나면 다시 한 회 차 탐색을 더 진행해야 했다. 여기서종료 조건을 어디다가 걸어주지.. 하고 이것저것 해보았던 것 같다.

 

더 공부를 해야겠다...