[BOJ/Java] 16234 : 인구이동

 

문제

 

 

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

 

풀이

 

 

처음에 조금 헤맸지만, 알고보니 쉬운 문제였다. BFS를 사용해 연결된 연합을 찾고 visited 처리해주어서 다시 방문하지 않도록 한다. 연합을 찾을 때마다 해당 맵을 update 해준다!

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int N, L, R;
	static boolean isMove;
	static boolean[][] visited;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.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(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int count = 0;

		while (true) {
			visited = new boolean[N][N];
			isMove = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j]) { //방문하지 않은 곳에 BFS를 돌림
						BFS(i, j);
					}
				}
			}
			if (!isMove) //인구이동이 일어나지 않았으면 break
				break;
			count++;
		}

		System.out.println(count);
	}

	private static void BFS(int i, int j) {
		Queue<Node> moveArea = new LinkedList<>();//이동한 영역 list
		Queue<Node> queue = new LinkedList<>();//bfs를 위한 큐 

		queue.add(new Node(i, j));
		moveArea.add(new Node(i, j));

		visited[i][j] = true;
		int sum = 0;
		sum += map[i][j];

		while (!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.peek().y;
			queue.poll();
			for (int d = 0; d < 4; d++) {
				int dx = x + dir[d][0];
				int dy = y + dir[d][1];
				if (dx < 0 || dy < 0 || dx >= N || dy >= N)
					continue;
				if (visited[dx][dy])
					continue;
				int diff = Math.abs(map[x][y] - map[dx][dy]);
				if (diff >= L && diff <= R) { // 이웃 나라와의 차가 L이상 R이하일 때

					visited[dx][dy] = true;//해당 나라 방문
					moveArea.add(new Node(dx, dy));//인구이동할 list에 넣어줌
					queue.add(new Node(dx, dy));
					sum += map[dx][dy];//연합의 총 인구를 구하기 위해 더해줌
				}

			}
		}

		int avg = 0;
		if (moveArea.size() > 1) { //연합이 만들어졌다면(인구이동이 일어날 수 있다면)
			avg = sum / moveArea.size();
			isMove = true;
			
			while (!moveArea.isEmpty()) {//연합 내에 있는 나라 인구를 평균값으로 바꿔줌
				map[moveArea.peek().x][moveArea.peek().y] = avg;
				moveArea.poll();
			}
		}
	}

	static class Node {
		int x, y;

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

		}
	}
}

 

 

느낀점

 

• 스스로 생각하는게 어렵다 ㅠㅠ