[삼성SW테스트] 백준 16234 인구이동(DFS)

 

 

 

백준 DFS 문제

#16234- 인구이동

 

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

 

 

사용한 개념

 

DFS 문제입니다. BFS로도 할 수 있을 것 같은데, 저는 DFS 재귀 연습도 할겸 DFS 했습니다. 연합을 이룰 수 있는 국가를 구하고, 연합 국가의 총 인구수와 국가를 나누는 간단한 DFS문제입니다.

 

제가 생각한 프로세스는 다음과 같습니다.

 

1. DFS로 조건에 맞는 연합국가를 구한다.

2. DFS탐색시 조건에 맞는 국가는 Sticker를 붙여서 연합국을 구별하도록 한다.

3. 각 연합국안에서 인구이동 실시.

4. 1-3 계속 반복...더이상 인구이동이 없을 때까지...

 

딱히 어려운건 아니였으나...시간차를 두고 풀어봤는데, 다르게 소스를 짰네요...ㅎㅎ..

간혹 시간초과가 뜨는데...연합국이 없는 경우엔 인구이동 없이 바로 스킵하는 것이 시간초과를 방지한다는 것만 기억하면 좋을 것 같습니다...

 

음..항상..프로세스 단계를 수행하는 것이 좋지만. 조건이 맞지 않는 경우 다음 단계를 진행할 필요가 없습니다. 그런 예외 케이스를 생각하는 것이 알고리즘 시간효율성에 중요합니다.

 

 

2번째 푼 소스 (2019-03)

 

전체소스

package RESAMSUNG;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BackJoon_16234 {

	static int dX[] = {-1, 0, 1, 0};
	static int dY[] = {0, 1, 0, -1};
	static int N,L,R = 0;
	static int sum = 0;
	static int num = 0;
	static boolean goStop = true;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine(); 
		String[] strArr = str.split(" ");
		N = Integer.parseInt(strArr[0]);
		L = Integer.parseInt(strArr[1]);
		R = Integer.parseInt(strArr[2]);
		
		 int map[][] = new int[N][N];
		 for(int i=0; i<map.length; i++){
			 String str1 = br.readLine(); 
			 String[] strArr1 = str1.split(" ");
			 for(int j=0; j<map[0].length; j++){
				 map[i][j] = Integer.parseInt(strArr1[j]);
			 }
		 }
	
		 int ans = 0;
		 while (true) {
			 goStop = true;
			 int[][] check = new int[N][N];
			 int sticker = 1;
			 for(int i=0; i<map.length; i++){
				 for(int j=0; j<map[0].length; j++){
					 if(check[i][j] == 0){
						 search(map, check, i, j, sticker);
						 if(num != 1){
							 goStop = false;
							 int newPeopleNum = sum/num;
							 for(int a=0; a<map.length; a++){
								 for(int b=0; b<map[0].length; b++)
									 if(check[a][b] == sticker) map[a][b] = newPeopleNum;
							 }
						 }
						 sum = 0;
						 num = 0;
						 sticker++;
					 }
				 }
			 }
			 if(goStop) break;
			 ans++;
		}
		System.out.println(ans);
	}

	private static void search(int[][] map, int[][] check, int x, int y, int sticker) {
		check[x][y] = sticker;
		sum += map[x][y];
		num ++;
		
		for(int i=0; i<4; i++){
			int nX = x + dX[i];
			int nY = y + dY[i];
			if(-1<nX && nX<map.length && -1<nY && nY<map[0].length && check[nX][nY] == 0){
				int gap = Math.abs(map[x][y] - map[nX][nY]);
				if(L<=gap && gap<=R)
				search(map, check, nX, nY, sticker);		
			}
		}		
	}

}

 

 

2번째 푼 소스 (2019-02)

 

전체소스

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int[] sumList = new int[1000000];
	static int[] numList = new int[1000000];
	static int[] dX = {0, -1, 0, 1};
	static int[] dY = {-1, 0, 1, 0};
	static boolean finish = true;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int L = sc.nextInt();
		int R = sc.nextInt();
		
		int [][]map = new int[n][n];
			
		for(int i=0; i<map.length; i++){
			for(int j=0; j<map[0].length; j++){
				map[i][j] = sc.nextInt();
			}
		}
		
	//	for(int i=0; i<map.length; i++)System.out.println(Arrays.toString(map[i]));
		int ans = 0;
		while (finish) {	
			Arrays.fill(sumList, 0);
			Arrays.fill(numList, 0);
			
			int [][]check = new int[n][n];
			int index = 1;
			for(int i=0; i<map.length; i++){
				for(int j=0; j<map[0].length; j++){
					if(check[i][j] == 0){
						DFS(map, check, i, j, L, R, index);
						index++;
					}
				}
			}
			goPerson(map, check, index-1);
			ans++;
		}
		System.out.println(ans-1);
		
	}

	private static void goPerson(int[][] map, int[][] check, int index) {
		int cnt = 0;
		for(int i=1; i<=index; i++){
			if(cnt < numList[i]) cnt = numList[i];
			sumList[i] = sumList[i]/numList[i];
			//System.out.println(sumList[i]);
		}
		for(int i=0; i<check.length; i++){
			for(int j=0; j<check[0].length; j++){
				map[i][j] = sumList[check[i][j]];
			}
		}
		
		if(cnt < 2) finish = false;	
	}

	private static void DFS(int[][] map, int[][] check, int x, int y, int L, int R, int index) {
		check[x][y] = index; 
		sumList[index]+= map[x][y];
		numList[index]++;
		
		for(int i=0; i<4; i++){
			int nX = x + dX[i];
			int nY = y + dY[i];
			if(-1<nX && nX<map.length && -1<nY && nY<map[0].length && check[nX][nY] == 0){
				int C = Math.abs(map[x][y]-map[nX][nY]);
				if(L<=C && C<=R){
					DFS(map, check, nX, nY, L, R, index);
				}
			}
		}
		
	}

}

 

질문은 댓글에 남겨주세요~