BFS (백준 16234 인구이동)

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

16234번: 인구 이동

 

 

풀이순서

0. 하루마다 NxN크기의 땅을 확인하며 국경을 허물었는지 확인

while(true){
            if(!solve()){ // 국경 허물 수 있는지 확인하고 국경 허물고 인구수 갱신
                break;
            }
            ans+=1;
        }

• 하루마다 (0,0)에서 bfs를 수행하며 국경을 허물고 인구를 이동시켰다.

static boolean solve(){
        visited = new boolean[N][N];
        int flag = 0; // 국경을 허물었는지 확인하는 flag 변수

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visited[i][j]){
                    visited[i][j] = true;
                    int[] result = bfs(i,j); // bfs를 돌면서 국경을 허물고 (도시의 갯수, 도시 인구수 합) 을 반환
                    if(result[0] > 1){ // 벽을 허문 적이 있으면
                        spread(result[1]/result[0]); // history 큐 활용해서 인구이동 시키기
                        flag = 1;
                    }
                }
            }
        }

        if(flag==1) return true;

        return false;
    }

• 보통의 bfs함수와 비슷하지만 반환값으로 (국경 허문 도시의 갯수, 허문 도시 인구수의 합) 을 리턴해줬다.
• bfs함수 : 국경을 허물기
• spread함수 : 허물어진 국가 인구수 갱신

 

1. BFS를 수행하여 국경을 허물기

static int[] bfs(int r,int c){
        Deque<int[]> q = new ArrayDeque<>();
        history = new ArrayDeque<>(); // bfs수행 할 때 이동 했던 경로를 저장하고 있는 큐

        q.offer(new int[]{r,c});
        history.offer(new int[]{r,c});

        int cnt = 0;
        int sum = 0;

        while(!q.isEmpty()){
            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            cnt+=1;
            sum += arr[cr][cc];

            for(int d=0;d<4;d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                if(nr<0 || nr>=N) continue;
                if(nc<0 || nc>=N) continue;
                if(visited[nr][nc]) continue;

                int gap = Math.abs(arr[cr][cc] - arr[nr][nc]);
                if(gap<L || gap>R) continue;

                visited[nr][nc]=true;
                q.offer(new int[]{nr,nc});
                history.offer(new int[]{nr,nc}); // 큐가 방문한 위치들 다 저장

            }
        }

        return new int[]{cnt,sum};

    }

• 국경을 허물면서, 방문한 도시의 갯수(cnt)와 인구수의 합(sum)을 저장하고 리턴
• history큐에 방문한 좌표들을 저장 (국경이 허물어진 국가 인구수 갱신을 위해서)

 

2. 국경이 허물어진 나라들의 인구수를 update해주기 (history큐 활용)

static boolean solve(){
        visited = new boolean[N][N];
        int flag = 0; // 국경을 허물었는지 확인하는 flag 변수

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visited[i][j]){
                    visited[i][j] = true;
                    int[] result = bfs(i,j); // bfs를 돌면서 국경을 허물고 (도시의 갯수, 도시 인구수 합) 을 반환
                    if(result[0] > 1){ // 벽을 허문 적이 있으면
                        spread(result[1]/result[0]); // history 큐 활용해서 인구이동 시키기
                        flag = 1;
                    }
                }
            }
        }

        if(flag==1) return true;

        return false;
    }

• result[0] 값 즉 cnt값을 통해서 국경을 허물었다면, spread 함수에서 인구수를 갱신해줬다.
• flag변수를 통해 이번 하루동안 국경을 허문 경우가 있다면 true, 아니면 false를 리턴했다.

static void spread(int val){
        while(!history.isEmpty()){
            int[] a = history.pollFirst();
            arr[a[0]][a[1]] = val;
        }
    }

• bfs 함수에서 저장해줬던 history큐를 이용

---

bfs를 한 번 수행하는 것이 아닌 (0,0)부터 계속 새롭게 수행한다는 점에서 새로운 문제였다.

또 인구수 갱신을 위해 history큐에 방문한 좌표를 저장해줘야 시간초과를 피할 수 있었다.

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;


public class Main {

    static int N,L,R;
    static int[][] arr;
    static boolean[][] visited; // bfs 수행 시 사용할 visited 배열
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    static int ans;
    static Deque<int[]> history;


    static int[] bfs(int r,int c){
        Deque<int[]> q = new ArrayDeque<>();
        history = new ArrayDeque<>(); // bfs수행 할 때 이동 했던 경로를 저장하고 있는 큐

        q.offer(new int[]{r,c});
        history.offer(new int[]{r,c});

        int cnt = 0;
        int sum = 0;

        while(!q.isEmpty()){
            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            cnt+=1;
            sum += arr[cr][cc];

            for(int d=0;d<4;d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                if(nr<0 || nr>=N) continue;
                if(nc<0 || nc>=N) continue;
                if(visited[nr][nc]) continue;

                int gap = Math.abs(arr[cr][cc] - arr[nr][nc]);
                if(gap<L || gap>R) continue;

                visited[nr][nc]=true;
                q.offer(new int[]{nr,nc});
                history.offer(new int[]{nr,nc}); // 큐가 방문한 위치들 다 저장

            }
        }

        return new int[]{cnt,sum};

    }

    static void spread(int val){
        while(!history.isEmpty()){
            int[] a = history.pollFirst();
            arr[a[0]][a[1]] = val;
        }
    }
    static boolean solve(){
        visited = new boolean[N][N];
        int flag = 0; // 국경을 허물었는지 확인하는 flag 변수

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visited[i][j]){
                    visited[i][j] = true;
                    int[] result = bfs(i,j); // bfs를 돌면서 국경을 허물고 (도시의 갯수, 도시 인구수 합) 을 반환
                    if(result[0] > 1){ // 벽을 허문 적이 있으면
                        spread(result[1]/result[0]); // history 큐 활용해서 인구이동 시키기
                        flag = 1;
                    }
                }
            }
        }

        if(flag==1) return true;

        return false;
    }

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

        arr = new int[N][N];
        ans = 0;

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


        while(true){
            if(!solve()){ // 국경 허물 수 있는지 확인하고 국경 허물고 인구수 갱신
                break;
            }
            ans+=1;
        }

        System.out.println(ans);

    }

}