[BAEKJOON_16234 - JAVA] 인구 이동

 

 

풀이

• map을 돌며, 연합을 찾는것 -> BFS 활용.
• visit관리를 boolean이 아닌 int형으로 체크하면서 -> 인구이동 발생과 동일. (visit과 반복회수 동시에 관리)
• 연합의 좌표값을 Queue에 넣어 일괄적으로 관리.
• 연합에 넣을 값 = Queue의 사이즈로 계산

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class pair {
    int row, col;
    public pair(int row, int col) {
        super();
        this.row = row;
        this.col = col;
    }
}
public class Main {
    static int N, L, R, count, ch;
    static int[] dy = { -1, 1, 0, 0 }; // 상 하 좌 우
    static int[] dx = { 0, 0, -1, 1 };
    static int[][] map;
    static int[][] visited;
    static boolean check;
    static boolean isValid(int row, int col) {
        if (row < 0 || row >= N || col < 0 || col >= N)
            return false;
        return true;
    }
    static void bfs(int row, int col) {
        visited[row][col] = ch; // visit 체크
        int sum = map[row][col]; // 조건에 해당되는 배열 합
        Queue<pair> q = new LinkedList<pair>(); // bfs 좌표
        Queue<pair> pos = new LinkedList<pair>(); // 연합 좌표
        q.offer(new pair(row, col));
        pos.offer(new pair(row, col));
        while (!q.isEmpty()) {
            int q_row = q.peek().row;
            int q_col = q.peek().col;
            q.poll();
            // 사방 탐색
            for (int k = 0; k < 4; k++) {
                int next_row = q_row + dy[k];
                int next_col = q_col + dx[k];
                if (!isValid(next_row, next_col) || visited[next_row][next_col] == ch // 범위, 방문, 조건 2가지 검사
                        || Math.abs(map[q_row][q_col] - map[next_row][next_col]) < L
                        || Math.abs(map[q_row][q_col] - map[next_row][next_col]) > R)
                    continue;
                q.offer(new pair(next_row, next_col));
                pos.offer(new pair(next_row, next_col));
                sum += map[next_row][next_col];
                visited[next_row][next_col] = ch;
                check = true;
            }
        }
        if (pos.size() == 0) // 변화가 없다면, 종료
            return;
        int avg = sum / pos.size(); // 평균 = 연합의 합 / 크기
        while (!pos.isEmpty()) {
            map[pos.peek().row][pos.peek().col] = avg; // 연합 좌표에 값을 대입
            pos.poll();
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        count = 0;
        ch = 0;
        check = true;
        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];
        visited = 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());
            }
        }
        // ======================= 입력 =======================
        while (check) {
            ch++; // visit 관리
            check = false; // 연합 관리
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (visited[i][j] != ch) { // visit 여부
                        bfs(i, j);
                    }
                }
            }
        } // end of while
        ch--; // 시작하자마자 더한 이동횟수 제외
        System.out.println(ch);
    } // end of main
} // end of class