BOJ 16234번: 인구 이동

문제

문제 바로가기> BOJ 16234번: 인구이동

16234번: 인구 이동

 

풀이

문제의 요구사항을 구현해주면 되는 간단한 문제였다.

 

1. 연합을 구하기 위해 그래프 탐색 (DFS or BFS) 진행

2. 연합의 크기 > 1 인 경우, 인구 이동

    연합의 크기 < 1 인경우, break ; 정답 출력

 

크게 위와 같은 2가지 과정으로 이루어지는데,

연합을 구하기 위해 DFS를 사용했을 때가 BFS를 사용했을 때 보다 시간이 훨씬 줄어들었다.

 

그 이유를 찾아보니 ...

DFS함수보다 BFS가 메모리와 시간이 더 필요로 한다고 한다.

BFS를 진행할 때, queue에서 넣고 꺼내고 복사하는 과정이 느리다고 ... !

DFS는 어떻게든 찾기만 하면 될 때 쓰고, BFS는 탐색 시 이동 횟수가 최소인 것을 찾을 때 쓰는 느낌이라고,, 했다 ㅎㅎ

 

C++

#include<iostream>
#include<cstring>
#include<vector>
#define MAX 51
using namespace std;

int total;
int N, L, R;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
vector<pair<int, int>> pos;

void input(){
    cin >> N >> L >> R;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) cin >> map[i][j];
    }
}

void make_union(int y, int x){
    visited[y][x] = true;
    pos.push_back({y, x});

    for(int d=0; d<4; d++){
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>=N || nx<0 || nx>=N || visited[ny][nx]) continue; // 범위를 벗어나는 경우, 이미 방문한 경우
        int diff = abs(map[y][x]-map[ny][nx]); // 국경선을 공유하는 두 나라의 인구 차
        if(L<=diff && diff<=R){ // L명 이상, R명 이하인 경우
            total+=map[ny][nx];
            make_union(ny, nx);
        }
    }
}

void solution(){ // 인구 이동이 며칠 동안 발생하는지

    int ans = 0;
    while(true){
        
        memset(visited, false, sizeof(visited)); // init
        
        bool ismove = false;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visited[i][j]) continue;
                pos.clear();
                total = map[i][j];
                make_union(i, j); // 연합을 이루고

                if(pos.size() == 1) continue;
                
                // 인구 이동
                ismove = true;
                int avg = total/(int)pos.size();
                for(int p=0; p<(int)pos.size(); p++){
                    int y = pos[p].first;
                    int x = pos[p].second;
                    map[y][x] = avg;
                }
            }
        }
        if(!ismove) break; // 인구 이동이 발생하지 않는 경우
        ans++; // 인구 이동이 발생한 경우
    } 
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}

 

Java

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

public class Main {
	
	private static int dy[] = {0, -1, 0, 1};
	private static int dx[] = {1, 0, -1, 0};
	private static int N, L, R, total;
	
	private static int[][] map;
	private static boolean[][] visited;
	static List<int[]> pos = new ArrayList<int[]>();

	public static void main(String[] args) throws Exception {

		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());
		
		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());
			}
		}
		solution();
	}

	private static void solution() {
	    int ans = 0;
	    while(true){
	        
	        visited = new boolean[N][N];
	        
	        boolean ismove = false;
	        for(int i=0; i<N; i++){
	            for(int j=0; j<N; j++){
	                if(visited[i][j]) continue;
	                pos = new ArrayList<int[]>();
	                total = map[i][j];
	                make_union(i, j); // 연합을 이루고

	                if(pos.size() == 1) continue;
	                
	                // 인구 이동
	                ismove = true;
	                int avg = total/(int)pos.size();
	                for(int p=0; p<(int)pos.size(); p++){
	                    int y = pos.get(p)[0];
	                    int x = pos.get(p)[1];
	                    map[y][x] = avg;
	                }
	            }
	        }
	        if(!ismove) break; // 인구 이동이 발생하지 않는 경우
	        ans++; // 인구 이동이 발생한 경우
	    } 
	    System.out.println(ans);
	}

	private static void make_union(int y, int x){
	    visited[y][x] = true;
	    pos.add(new int[] {y,x});

	    for(int d=0; d<4; d++){
	        int ny = y+dy[d];
	        int nx = x+dx[d];
	        if(ny<0 || ny>=N || nx<0 || nx>=N || visited[ny][nx]) continue; // 범위를 벗어나는 경우, 이미 방문한 경우
	        int diff = Math.abs(map[y][x]-map[ny][nx]); // 국경선을 공유하는 두 나라의 인구 차
	        if(L<=diff && diff<=R){ // L명 이상, R명 이하인 경우
	            total+=map[ny][nx];
	            make_union(ny, nx);
	        }
	    }
	}

}