[알고리즘] 백준16234 인구 인동 - 자바

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

16234번: 인구 이동

 

 

[풀이 코드]

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 {
	static int N, L, R, day;
	static int[][] map;
	static boolean[][] visited;
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {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());
			}
		}
		
		while(check()) {
			day++;
		}
		
		System.out.println(day);
		
	}
	
	private static boolean check() {
		boolean flag = false;
		visited = new boolean[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j] && bfs(i, j)){
					flag = true;
				}
			}
		}
		return flag;
	}

	private static boolean bfs(int i, int j) {
		Queue<Point> q = new LinkedList<>();
		Queue<Point> unionQ = new LinkedList<>();
		visited[i][j] = true;
		q.offer(new Point(i, j));
		unionQ.offer(new Point(i, j));
		int sum=map[i][j];
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int d=0; d<4; d++) {
				int y = p.y + dy[d];
				int x = p.x + dx[d];
				if(y>=0 && x>=0 && y<N && x<N && !visited[y][x]) {
					int diff = Math.abs(map[p.y][p.x] - map[y][x]);
					if(diff >= L && diff <= R) {
						q.offer(new Point(y, x));
						unionQ.offer(new Point(y, x));
						visited[y][x] = true;
						sum += map[y][x];
					}
				}
			}
			
		}
		
		int num = sum / unionQ.size();
		if(unionQ.size()>1) {
			Move(unionQ, num);
			return true;
		}
		
		return false;
	}
	
	private static void Move(Queue<Point> q, int sum) {
		while(!q.isEmpty()) {
			Point p = q.poll();
			map[p.y][p.x] = sum;
		}
	}

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

 

1. while() 문 안에서 check() 함수를 통해 인구이동이 가능한지 먼저 체크한다.
2. check() 문 안에서 이중 for문을 돌며 bfs() 함수를 수행하는데 이때 방문 배열 visited를 신경 써야 한다.
3. bfs() 문 안에서는 두 개의 큐를 썼는데 q는 이동 가능한 좌표를 담고 unionQ는 연결되는 땅을 담는다. 
   1. unionQ에 하나 이상 연결된 땅이 있다면 Move() 함수를 통해 map을 문제에서 주어진 방식대로 변경시켜준다.

 

싸피에서 친해진 알고리즘 스승님께 혼나가며 배우는 중... 요새 나를 놀리는 데 재미 들리신 것 같다..ㅜ 많이 배우는 중👍👍

https://kkap999.tistory.com/category/%ED%94%8C%EB%B0%8D

'플밍' 카테고리의 글 목록