16234 인구이동 - 삼성 sw 역량 기출

인구이동

한 턴마다 칸마다의 인구차이가 L 이상 R 이하이면 국경선을 개방해 연결된 칸들의 평균으로 맵을 구성하여 인구이동이 없을 때까 지 총 몇턴이 지났는지 구하는 문제이다.

1. dfs구현
   dfs를 이용하여 현재 칸 부터 연결될 수 있는 모든 칸을 구한다.
   dfs 함수가 시작되면 현재 칸을 방문처리하고 현재 칸의 좌표를 리스트에 저장한다.
   또한, sum에 현재 칸의 값을 더해주어 dfs한 번에서 나올수 있는 합계를 구할 수 있도록 한다.
   여기서 이번턴에 방문 했거나 조건에 맞지 않는 칸은 방문하지 않도록 설정
   

2. dfs 실행
   main에서 모든 칸 부터 dfs를 실행할 수 있도록 한다.
   방문한 칸은 dfs를 실행하지 않는다.
   

3. 턴 수 계산
   1-2번을 한 턴으로 잡고 처리한다.
   계속 턴이 지날 수 있도록 1-2를 while로 묶어준다.
   chk전역변수를 만들어 dfs 내부에서 국경선이 열리게 될 때는 true로 바꿔주어서 chk가 false일 때 while이 종료되도록 구현한다.
   while이 한 번 돌때마다 cnt를 올려주고 while문이 끝나면 출력해준다.
   

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main인구이동 {
	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());

		int[][] map = new int[N][N];

		for(int i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
			}
		}

		chk = false;
		int cnt = 0;
		while(true) {

			chk = false;
			visited = new boolean[N][N];

			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						add = new ArrayList<>();
						sum = 0;
						dfs(map, i, j);
						for(int k = 0; k < add.size(); k++) {
							map[add.get(k)[0]][add.get(k)[1]] = sum/add.size();
						}
					}
				}
			}
			cnt++;

			if(!chk) {
				break;
			}
		}


		System.out.println(cnt-1);
	}

	static int[] dy = {0,0,-1,1};
	static int[] dx = {1,-1,0,0};
	static int L;
	static int R;
	static int N;
	static boolean[][] visited;
	static List<int[]> add;
	static int sum;

	static boolean chk;


	static void dfs(int[][] map, int y, int x) {
		visited[y][x] = true;
		add.add(new int[] {y,x});
		sum += map[y][x];
		for(int i = 0; i < 4; i++) {
			int yi = dy[i]+y;
			int xi = dx[i]+x;

			if(yi < 0 || yi >= N || xi < 0 || xi >= N || visited[yi][xi])continue;

			if(Math.abs(map[yi][xi] - map[y][x]) >= L && Math.abs(map[yi][xi] - map[y][x]) <= R) {
				chk = true;
				dfs(map, yi, xi);
			}

		}

	}
}