16234번 : 인구 이동 (JAVA)

LOGIC

1. 모든 맵의 위치에서
2. 방문하지 않은 나라라면
3. dfs로 주위 연합 찾기
4. 방문하지 않았고 범위 안에 있는 옆 나라라면, 두 나라 사이의 갭을 구하기
5. 갭이 범위 안에 있다면, 해당 나라 큐와 연합 리스트에 집어 넣기
6. 큐에 남은 나라가 없다면
   • 연합이 있었다면 연합의 인구 수 평균을 구해서 나눠주기
7. 모든 배열을 체크 했을 때 까지 반복

---

CODE

package baekjoon16234;

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

public class Main2 
{
	static class Country
	{
		int posX;
		int posY;

		public Country(int posX, int posY) {
			super();
			this.posX = posX;
			this.posY = posY;
		}
	}

	static int direction[][] = {{-1, 0},{1, 0},{0, -1},{0, 1}};
	static boolean isVisited[][];
	static int map[][];
	static int N, min, max, answer = 0;
	static boolean isUnion = 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());//1 ≤ N ≤ 50
		min = Integer.parseInt(st.nextToken());//1 ≤ L ≤ R ≤ 100
		max = Integer.parseInt(st.nextToken());//1 ≤ L ≤ R ≤ 100
		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(true)
		{
			isUnion = false;
			isVisited = new boolean[N][N];

			for(int i = 0; i<N; i++)
			{
				for(int j = 0; j<N; j++)
				{
					if(!isVisited[i][j])//방문하지 않았다면
					{
						 bfs(new Country(i, j));//i, j 주변 탐색
					}
				}
			}

			if(isUnion) answer++; //연합이 있다면 답에 1더하기
			else //연합이 없다면
			{
				System.out.println(answer); //답 출력
				break;//반복문 나가기
			}
		}
	}

	private static void bfs(Country startCountry) 
	{
		Queue<Country> queue = new LinkedList<>();//bfs 탐색을 기다리는 큐
		List<Country> union = new ArrayList<>();//연합의 정보를 담고있는 리스트
		queue.offer(startCountry);//시작 나라 삽입
		union.add(startCountry);//시작 나라 삽입

		//방문 체크
		isVisited[startCountry.posX][startCountry.posY] = true;
		int sum = map[startCountry.posX][startCountry.posY];//연합 총 인구수에 인구수 더하기
		int count = 1;//나라 수 세기

		boolean isCurrentUnion = false;//연합 유무 체크

		while(!queue.isEmpty())
		{
			Country currentCountry = queue.poll();
			for(int i = 0; i<direction.length; i++)
			{
				int nextX = currentCountry.posX + direction[i][0];
				int nextY = currentCountry.posY + direction[i][1];

				//범위를 벗어났거나, 방문한적 있으면 반복문 나가기
				if(nextX<0 || nextX>=N || nextY<0 || nextY>= N || isVisited[nextX][nextY]) continue;
				
				//현재 나라와 현재 나라와 인접하고 있는 나라 인구 차이 계산
				int gap = Math.abs(map[currentCountry.posX][currentCountry.posY] - map[nextX][nextY]);
				
				//인구 차가 범위 안이라면
				if(gap>=min&&gap<=max)
				{
					isCurrentUnion = true;//연합 유무 체크
					isVisited[nextX][nextY] = true;//방문 체크
					queue.offer(new Country(nextX, nextY));//큐에 추가
					union.add(new Country(nextX, nextY));//연합 리스트에 추가
					sum+=map[nextX][nextY];//연합 총 인구수에 인구수 더하기
					count++;//연합 수 더하기
				}
			}
		}
		
		//연합이 만들어졌다면
		if(isCurrentUnion)
		{
			isUnion = true;//연합 만들어졌다고 알리기
			int value = sum/count;//평균 값 구하기

			for(int i = 0; i<union.size(); i++)
			{
				int x = union.get(i).posX;
				int y = union.get(i).posY;

				map[x][y] = value;//맵 갱신
			}

			union = new ArrayList<>();//연합 정보 초기화
		}
	}
}