[백준] 16234 인구이동

문제보기

간단하게 BFS로 풀어보았다.

국경선 오픈 조건(l, r) 이 성립하면 큐에 추가하는 방식이다.

다만 큐에 추가된 적이 있는 곳의 좌표를 따로 기록해놔야 나중에 인구를 재배치 할 수 있으므로 어딘가에 기록해두도록 하자.

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

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

public class Main {
	static int[][] map;
	static int n;
	static int l;
	static int r;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static boolean[][] check;
	
	static void bfs(int i, int j) {
		Queue<Pair> q = new LinkedList<>();
		check[i][j] = true;
		q.add(new Pair(i, j));
    // 연합이 될 국가의 좌표를 기억할 스택(꼭 스택이 아니어도 좋다)
		Stack<Pair> st = new Stack<Pair>();
		st.add(new Pair(i, j));
    // 연합의 총 인구수를 저장할 변수
		int sum = map[i][j];
		
		while(!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			
      // 네 방향에 대해 조사한다
			for(int k = 0 ; k < 4 ; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				// 다음 좌표는 맵 내에 존재해야 하며 방문한적이 없어야 한다.
				if(nx >= 0 && nx < n && ny >= 0 && ny < n && check[nx][ny] == false) {
          // 두 국가 간 인구 수의 차이
					int diff = Math.abs(map[nx][ny]-map[x][y]);
					// 차이가 l이상 r이하면 연합을 맺을 수 있다 
          if(diff >= l && diff <= r) {
						check[nx][ny] = true;
						q.add(new Pair(nx, ny)); // 큐에 추가
						st.add(new Pair(nx, ny)); // 연합 저장
						sum += map[nx][ny]; // 인구 수 더해주기
					}
				}
			}
		}
		if(st.size() == 1) return; // 연합이 단 한군데도 없다면 그냥 종료하자
		
		int size = st.size(); // 연합의 크기
		int move = sum/size; // 새로 배치될 국가 당 인구 수 
		while(!st.isEmpty()) {
			Pair p = st.pop();
			map[p.x][p.y] = move; // 새로 인구를 넣어준다 
		}
	}
	
  // 더이상 인구 이동이 가능할지 여부를 반환하는 함수
	static boolean hasMoreMove() {
    // 우측의 국가와 연합이 가능할까?
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n-1 ; j++) {
				int diff = Math.abs(map[i][j] - map[i][j+1]);
				if(diff >= l && diff <= r) {
					return true; // 가능하면 트루 반환
				}
			}
		}
		// 아래의 국가와 연합이 가능할까?
		for(int i = 0 ; i < n-1 ; i++) {
			for(int j = 0 ; j < n ; j++) {
				int diff = Math.abs(map[i][j] - map[i+1][j]);
				if(diff >= l && diff <= r) {
					return true; // 가능하면 트루 반환
				}
			}
		}
    // 이 모든 반복문에서 한번도 안걸렸다면 더이상 인구 이동이 불가능한 상태
		return false;
	}
	
	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());
			}
		}
		
		int cnt = 0;
    
		while(true) { // 계속 반복한다 
      // 더이상의 인구이동이 가능하다면 말이다
			if(!hasMoreMove()) break;
			// 방문 여부 초기화 
			check = new boolean[n][n];
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					if(check[i][j] == false) {
            // 방문한 적 없는 국가에 대하여 BFS 해주자
						bfs(i, j);
					}
				}
			}
      // 인구 이동이 끝났다. 카운트를 올리자! 
			cnt++;
		}
		System.out.println(cnt); // 최종 카운트 반환
	}
}