[백준] 16234 - 인구 이동 (JAVA)

개츠비·2023년 4월 6일

목록 보기

55/84

소요시간 : 1시간 30분
문제 사이트 : 백준
문제 수준 : 골드 5
문제 유형 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/16234
푼 날짜 : 2023.04.06

1. 사용한 자료구조 & 알고리즘

구현. dfs . 큐

2. 사고과정

가장 시간을 많이 보낸 부분:
(1) 0,0 좌표와 0,1의 좌표가 인구이동이 가능하다는 것을 어떻게 나타낼 것인가 ?
-> DFS 를 수행. 다음 좌표와 현재 좌표의 인구 차이를 보고 노드를 이어감.
(2) 인구 이동은 한 번에 처리해야 하는데 어떻게 처리할 것인가?
-> idx에 해당하는 queue 형 배열을 선언해서 각각 인구이동이 가능한 구역마다 좌표를 기억해 두었다가 나중에 for문이 끝나고 한 번에 이동하는 식으로 처리.

-> 처음에 시행착오를 얻은 부분 :
1.3 좌표와 1.2 좌표가 인구 이동이 가능하다는 것을 4차원 배열로

//4차원 배열 선언
boolean canMove[][][][]=new boolean[N][N][N][N]

//1.3과 1.2 좌표는 인구 이동이 가능하다
camMove[1][3][1][2] = true

시도해보려다가 메모리의 낭비와 내가 생각하지 못한 오류가 발생해서 철회 하는 과정에서 시간을 많이 소비함.

3. 풀이과정

현재 위치에서 dfs 수행. 수행할 때 마다 idx 번째 queue에 위치를, idx 번쨰 sum에 합계를 더함
50 * 50 개의 2차원 테이블을 모두 탐색했다면 0번째 부터 idx번째 queue만큼 기억해뒀던 해당 좌표 사람들의 인원수를 조정해줌.
만약 인구이동이 되지 않았다면 break

4. 소스코드

import java.util.*;
import java.io.*;

public class Main{

	static int people[][];
	static boolean visited[][];
	static int dy[]= {-1,0,1,0};
	static int dx[]= {0,-1,0,1};


	static int idx;
	static int sum[];
	static Queue <Integer[]> index[];

	static int L,R;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		sum=new int[2500];
		index=new LinkedList[2500];
		st=new StringTokenizer(br.readLine());

		int N=Integer.parseInt(st.nextToken());
		L=Integer.parseInt(st.nextToken());
		R=Integer.parseInt(st.nextToken());

		people=new int[N][N];

		for(int i=0;i<people.length;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<people.length;j++) {
				people[i][j]=Integer.parseInt(st.nextToken());
			}
		}

		int cnt=0;

		while(true) {

			idx=0;
			sum=new int[2500];
			visited=new boolean[N][N];
			for(int i=0;i<people.length;i++) {
				for(int j=0;j<people.length;j++) {

					index[idx]=new LinkedList<>();
					
					//방문했다면 continue
					if(visited[i][j]) continue;
					
					
					dfs(i,j);
					
					//dfs 했는데 탐색한게 없다면 continue
					if (index[idx].isEmpty()) continue;
	
					//탐색을 최소 1개 한 것이므로 현재 인구도 포함 시킴
					index[idx].add(new Integer[] {i,j});
					sum[idx]+=people[i][j];
	
					idx++;

				}
			}


			for(int i=0;i<idx;i++) {
			
			
				int result=sum[i]/index[i].size();

				while(!index[i].isEmpty()) {
					Integer temp[]=index[i].poll();
					people[temp[0]][temp[1]]=result;
				}


			}

			if(idx==0) break;

			cnt++;
		}

		System.out.println(cnt);

	}
	public static void dfs(int y,int x) {
		
		visited[y][x]=true;

		for(int i=0;i<4;i++) {
			int nextY=y+dy[i];
			int nextX=x+dx[i];
			if(nextY<0||nextX<0||nextY>=people.length||nextX>=people.length) continue;

			if(visited[nextY][nextX])
				continue;

			int diff=Math.abs(people[y][x]-people[nextY][nextX]);
			
			
			if(!(diff>=L&&diff<=R)) continue;

			
			index[idx].add(new Integer[] {nextY,nextX});
			sum[idx]+=people[nextY][nextX];
			dfs(nextY,nextX);
			
		}

	}
}