[BOJ 16234] 인구 이동

문제

• BOJ 16234
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

DFS로 풀어주었다.

1. map을 돌면서 아직 방문하지 않았다면 dfs()호출해서 이 좌표와 연결되는 나라를 찾는다.
2. dfs함수 내에서 방문처리하고 연결된 나라 개수,좌표값을 누적합한다.
   • 4중 for문을 돌면서 주변에 연결가능한 인접한 나라가 있는지 체크한다.
   • 현재 좌표값과 인접한 좌표값의 차이가 L이상 R이하라면 dfs()를 호출해 또 다른 연결되는 나라를 찾는다.
3. 다시 main으로 돌아와서 연결된 나라가 있다면(count!=1)라면 sum/count한 결과로 인구수를 변경해준다.
   • 모든 for문을 돌고난 후에도 isStop==true라면 연합이 생성되지 않았으므로 while문을 종료한다.

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


public class Main{

    static int N, L, R;
    static int[][] map;
    static int[][] visited; //방문했는지
    static int[] di = {0, 1, 0, -1};
    static int[] dj = {1, 0, -1, 0};
    static int count, sum;
    static int Ans;
    static boolean isStop;

    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());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        map = new int[L][R];

        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());
            }
        }//input map

        while(true){
            isStop = true;
            visited = new int[N][N];

            int num = 1;//생성된 연합 개수
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(visited[i][j]==0){//아직 방문x
                       dfs(i, j, num);
                       if(count!=1){ //다른 나라와 연결했다면
                           isStop = false;
                           int result = sum/count;
                           for(int r=0; r<N; r++){//연합 하나 만들때마다 인구 수 변경
                               for(int c=0; c<N; c++){
                                   if(visited[r][c]==num) map[r][c] = result;
                               }
                           }
                       }
                    }
                    count=0;
                    sum=0;
                    num++;
                }
            }//End 연합생성

            if(isStop) break;
            Ans++;
        }//인구이동 종료

        System.out.println(Ans);
    }

    private static void dfs(int r, int c, int num){
        visited[r][c] = num;
        count++; //나라 수
        sum += map[r][c]; //합

        //4방향 탐색
        for(int d=0; d<4; d++){
            int nr = r + di[d];
            int nc = c + dj[d];

            if(nr>=0 && nr<N && nc>=0 && nc<N && visited[nr][nc]==0){
                int dist = Math.abs(map[r][c] - map[nr][nc]);
                if(L<=dist && dist<=R){//차이가 L이상 R이하 일때
                    dfs(nr, nc, num);
                }
            }
        }
    }
}