BOJ - 인구 이동 16234번 (JAVA)

❓ 문제 - 백준 인구 이동 16234번 - JAVA 풀이법

출처 

(https://www.acmicpc.net/problem/16234)

16234번: 인구 이동

 

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)로 해결하는 것이다.

• 두 개의 큐를 이용해 전체 나라를 탐색을 위한 queue와 국경선을 공유한 것의 지역을 담을 queue2를 통해 해결
• 한 지역에 대해 국경선 공유할 때 연합인구수와 연합을 이루고 있는 국가 수를 저장하기 위해 cnt변수 이용
• queue에 존재할 때까지 connet queue에 국경선을 공유하여 연합한 국가들의 위치를 append, 연합인구수(people)에 map[x][y] 를 더하고 연합을 이루고 있는 국가수(cnt)를 +1 증가시켜줌
• 4방향을 돌면서 인접한 국가들과의 인구 수 차이(diff)를 계산하여 만약 diff가 주어진 L 이상 R 이하라면 국경선을 공유하기 위하여 visited로 방문 처리해주고, q에 국경선을 공유한 위치(nx, ny)를 append
• 국경선이 공유되는지 queue를 통해서 다 확인 후에, 위에서 구한 두 번째 큐에서 국경선을 공유한 지역에  연합인구수 // 연합을 이루고 있는 개수로 graph 값을 변경시켜줌
• bfs를 돌면서 count 즉, 국경선을 공유한 지역이 없다면 return 0
• bfs를 돌면서 count 즉, 국경선을 공유한 지역이 있다면 return 1
• 메인에서 while문 돌면서 국경선 공유 없을 때까지 인구이동 처리한다.

 

💻 소스코드

// BOJ - 인구이동(16234번)
// BFS

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

public class Main_16234 {
	public static int n, l, r;
	public static int[][] map;
	public static int[][] visited;
	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	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 ans = 0;
		while(true) {
			boolean check = false;
			boolean[][] visited = new boolean[n][n];

			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(!visited[i][j]) {
						int change = bfs(visited, i, j);
						if(change >= 2) {
							check = true;
						}
					}
				}
			}
		
			if(!check) {
				break;
			}

			ans++;
			
		}
		
		System.out.println(ans);
	}
	
	public static int bfs(boolean[][] visited, int x, int y) {
		Queue<Node> q = new LinkedList<>();
		Queue<Node> q2 = new LinkedList<>();
		visited[x][y] = true;
		q.add(new Node(x, y));
		q2.add(new Node(x, y));
		
		int cnt = 1;
		int sum = map[x][y];
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny]) {
						int diff = Math.abs(map[node.x][node.y] - map[nx][ny]);
						if(diff >= l && diff <= r) {
							cnt++;
							sum += map[nx][ny];
							visited[nx][ny] = true;
							q.add(new Node(nx, ny));
							q2.add(new Node(nx, ny));
						}
					}
				}
			}
		}

		if(cnt==1) {
			return 0;
		} 
		else {
			while(!q2.isEmpty()) {
				Node node = q2.poll();
				map[node.x][node.y] = sum / cnt;
			}
		}
		return cnt;
		
	}

}