[JAVA] 백준 인구이동

<테스트케이스1>

2 20 50

50 30

20 40

테스트케이스1

 

헛점으로 기록된 부분은 오른쪽/아래로 탐색하는데 유턴해서 돌아오는경우(아래 예시)

(0,1)     (0,2)

↓         ↑

(1,1)→  (1,2)

 

right값이나 down값으로 dfs를 엮을수 없다.

따라서 현재 좌표 위치에서

1. 왼쪽좌표의 right값이 true인지

2. 위의좌표의 down값이 true인지

 

를 통해서 추가로 확인해줌으로써 국경들을 모두 이을 수 있었다.

 

전체코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static People[][] map;
    static boolean[][] visit;
    static int N, L, R;

    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 People[N][N];
        visit = new boolean[N][N];

        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = new People(Integer.parseInt(st.nextToken()));
            }
        }
        while (true) {
            boolean check = start();
            if (check) count++;
            else {
                //System.out.println("break");
                break;
            }

        }
        System.out.println(count);
    }

    static int count = 0;
    static ArrayList<Loc> list = new ArrayList<>();

    static boolean start() {
        //System.out.println("start");
        visit = new boolean[N][N];
        boolean haveMoved = false;

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                People p = map[r][c];
                p.checkRight(r, c);
                p.checkDown(r, c);
            }
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (visit[r][c]) continue;

                list.clear();
                dfs(r, c);

                if (list.size() > 1) {
                    int sum = 0;
                    for (int i = 0; i < list.size(); i++) {
                        Loc l = list.get(i);
                        People p = map[l.r][l.c];

                        sum += p.val;
                    }
                    int average = sum / list.size();
                    //System.out.println(average + "list size:" +list.size());
                    for (int i = 0; i < list.size(); i++) {//평균값으로 setVal
                        Loc l = list.get(i);
                        //System.out.println(l.r+"/" + l.c);
                        map[l.r][l.c].setVal(average);
                        map[l.r][l.c].right = false;
                        map[l.r][l.c].down = false;

                    }
                    haveMoved = true;
                }
            }
        }
        return haveMoved;

    }

    static void dfs(int r, int c) {
        People p = map[r][c];
        visit[r][c] = true;
        list.add(new Loc(r, c));
        if (p.right && !visit[r][c + 1]) {
            dfs(r, c + 1);
        }

        if(c>=1) {
            People leftP = map[r][c - 1];
            if (leftP.right && !visit[r][c-1]){
                dfs(r,c-1);
            }
        }
        if (p.down && !visit[r + 1][c]) {
            dfs(r + 1, c);
        }

        if(r>=1) {
            People leftP = map[r-1][c];
            if (leftP.down && !visit[r-1][c]){
                dfs(r-1,c);
            }
        }
        return;
    }

    static class Loc {
        int r, c;

        Loc(int r, int c) {
            this.r = r;
            this.c = c;
        }

    }

    static class People {
        int val;
        boolean right = false,
                down = false;

        People(int val) {
            this.val = val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public void checkRight(int r, int c) {
            if (r >= 0 && r < N && c >= 0 && c < N - 1) {
                int thatVal = map[r][c + 1].val;
                if (Math.abs(thatVal - this.val) >= L && Math.abs(thatVal - this.val) <= R) {
                    right = true;
                }
            }
        }

        public void checkDown(int r, int c) {
            if (r >= 0 && r < N - 1 && c >= 0 && c < N) {
                int thatVal = map[r + 1][c].val;
                if (Math.abs(thatVal - this.val) >= L && Math.abs(thatVal - this.val) <= R) {
                    down = true;
                }
            }
        }
    }
}