[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 16234 : 인구 이동

 

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

문제 풀이

 

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

public class Main {
	
	static class Coord {  // coordinate
		int i, j;
		public Coord( int i, int j ) {
			this.i = i;
			this.j = j;
		}
	}
	
	public static void main(String[] args) throws IOException {
	
		int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    l = Integer.parseInt( st.nextToken() ), 
		    r = Integer.parseInt( st.nextToken() );
		int a[][] = new int[n][n];
		int i, j, k;
		for( i = 0; i < n; ++i ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < n; ++j )
				a[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		int c = 0, t, ni, nj, nni, nnj, d, s, p;  
		// cnt, next i/j, diff, sum, population
		boolean m[][][], v[][];  // migration, visited
		Queue<Coord> q;  // queue
		List<Coord> u; Coord co;  // union, coordinate
		while( true ) {
			t = 0;
			m = new boolean[n][n][4];
			for( i = 0; i < n; ++i ) {
				for( j = 0; j < n; ++j ) {
					for( k = 0; k < 4; ++k ) {
						if( m[i][j][k] )
							continue;
						ni = i + dx[k];
						nj = j + dy[k];
						if( ni < 0 || ni >= n || nj < 0 || nj >= n || 
						    m[ni][nj][k] )
							continue;
						d = Math.abs( a[i][j] - a[ni][nj] );
						if( d >= l && d <= r ) {
							m[i][j][k] = m[ni][nj][(k+2)%4] = true;
							t += 2;
						}
					}
				}
			}
			if( t == 0 )
				break;
			c++;
			v = new boolean[n][n];
			for( i = 0; i < n; ++i ) {
				for( j = 0; j < n; ++j ) {
					if( !v[i][j] ) {
						v[i][j] = true;
						s = 0;
						u = new ArrayList<>();
						q = new LinkedList<>();
						q.add( new Coord( i, j ) );
						while( !q.isEmpty() ) {
							co = q.remove();
							ni = co.i; nj = co.j;
							s += a[ni][nj];
							u.add( co );
							for( k = 0; k < 4; ++k ) {
								nni = ni + dx[k]; 
								nnj = nj + dy[k];
								if( nni < 0 || nni >= n || 
								    nnj < 0 || nnj >= n || 
								    v[nni][nnj] )
									continue;
								if( m[ni][nj][k] ) {
									v[nni][nnj] = true;
									q.add( 
									    new Coord( nni, nnj ) );
								}
							}
						}
						p = s / u.size();
						for( Coord cd : u )
							a[cd.i][cd.j] = p;
					}
				}
			}
		}
		System.out.println( c );
	}
}

 

*  int n, l, r, a[n][n] 입력 받음

*  국경선을 열고 인구 이동을 하는( 4 방향에 인접하는 두 나라의 인구 차이가 l명 이상, r명 이하인 ) 나라를 체크하기 위한 배열( boolean m[n][n][4] : migration ) 생성

*  무한 루프를 돌림

*  i행 j열 나라의 인구 수( a[i][j] )와 k방향으로 인접하는 ni행 nj열 나라의 인구수( a[ni][nj] )의 차이( abs() )가 l이상 r이하면 국경선을 열고 인구 이동을 한다( m[i][j][k] = m[ni][nj][(k+2)%4] = true )

 ( ni행 nj열 나라 입장에서는 반대 방향이므로 )

*  인구 이동을 하는 나라들의 개수( t )가 0이면( 인구 이동이 없으면 ) 무한 루프를 종료함

*  좌표 값으로 구성된 Coord 클래스 생성

*  i행 j열 나라들을 탐색하며 방문하지 않았으면( !v[i][j] ) 국경선이 열린 인접한 나라들을 BFS 하여 연합을 이룸( 인구 수 합 구하고, 리스트( List<Coord> u )에 위치 넣음

*  인구 이동을 할 때마다,

*  인구 이동 횟수( c )를 출력