Baekjoon[16234] - 인구 이동

링크

16234번: 인구 이동

 

문제설명

• 인접 칸과의 값 차이가 특정 범위 안이면 연결되어 인구가 이동하여 평균이 된다.

문제풀이

• 그래프의 연결성 문제, DFS가 좋대서 DFS로품.

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main16234 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Ans;
    public static int Temp;
    public static int Avg;
    public static boolean moved;

    public static int N;
    public static int L;
    public static int R;
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<int[]> link = new ArrayList<int[]>();

    public static void DFS(int[]rc) {
        visited[rc[0]][rc[1]]=true;
        Temp+=map[rc[0]][rc[1]];
        link.add(rc);

        int nr;
        int nc;
        int diff;
        for (int d = 0; d < 4; d++) {
            nr = rc[0] + dir[d][0];
            nc = rc[1] + dir[d][1];
//            경계 내에서, 다음칸이 방문 가능할 때, 옆 칸과 값 차이가 L과 R사이
            if(nr>=0 && nr<N && nc>=0 && nc<N && !visited[nr][nc]) {
                diff = Math.abs(map[rc[0]][rc[1]]-map[nr][nc]);
                if(diff>=L && diff<=R) {
                    DFS(new int[] {nr,nc});
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/16234.txt"));
        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());
            }
        }

        int lsize;
        int[] now;
        while(true) {
            moved=false;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(!visited[i][j]) {
                        link.clear();
                        Temp=0;
                        DFS(new int[] {i,j});
                        lsize = link.size();
                        Avg = Temp/lsize;
                        if(lsize>1) {
                            moved=true;
                            for (int l = 0; l < lsize; l++) {
                                now = link.get(l);
                                map[now[0]][now[1]]=Avg;
                            }
                        }
                    }
                }
            }
            if(moved) {
                Ans++;
            }
            else {
                break;
            }
        }

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• O(N) 고려안했음
  • N=50, Map=2500, DFS O(N)은 몇이지?
• while문에서 움직여야 Ans++인데 안움직여도 Ans++하게 했었음.
• 다음칸 탐색할 때, 옆 칸과의 차이 diff를 구할 때 경계검사 이전에 정의해서 경계검사안하고 터지는 경우 생겼었음.

잘한점

• 시간(25분)
• 그래프의 연결성 문제인 것을 알았음
• 연결된 그래프들은 list에 저장 후 따로 평균치 넣어주기
• 연결시킨 그래프들 제외하기위해서 visit 고려했음