[BOJ/Java] 16234. 인구 이동

[BOJ/Java] 16234. 인구 이동

16234번: 인구 이동

---

풀이

package edu.ssafy.im.BOJ.No16234;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static int[][] graph;
    static int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    static int n, l, r;
    static boolean[][] visited;
    static int[][] union;
    static int[][] unionNum;

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    public void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 입력 받기
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        graph = new int[n][n];
        union = new int[n][n];
        // 각 나라의 인구수 입력
        for (int x = 0; x < n; x++) {
            input = br.readLine();
            st = new StringTokenizer(input);
            for (int y = 0; y < n; y++) {
                graph[x][y] = Integer.parseInt(st.nextToken());
                union[x][y] = graph[x][y]; // 연합 정보 초기화
            }
        }

        int day = 0; // 인구 이동이 시작되는 날
        while (true) {
            visited = new boolean[n][n]; // 방문 여부 초기화
            unionNum = new int[n][n]; // 연합 번호 초기화
            int unum = 0; // 연합 번호
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (!visited[x][y]) {
                        unum++;
                        bfs(x, y, unum); // BFS를 통해 연합 형성
                    }
                }
            }

            boolean flag = true; // 모든 나라의 인구 이동이 종료되었는지 여부를 나타내는 플래그
            L: for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (graph[x][y] != union[x][y]) {
                        flag = false; // 인구 이동이 종료되지 않음
                        break L;
                    }
                }
            }

            if (flag) {
                sb.append(day); // 모든 나라의 인구 이동이 종료되면 결과 출력 후 종료
                break;
            }

            // 연합 정보 업데이트
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    graph[x][y] = union[x][y];
                }
            }

            day++; // 다음 날로 넘어감
        }

        System.out.print(sb); // 결과 출력
    }

    public void bfs(int x, int y, int unum) {
        Deque<Point> deque = new ArrayDeque<>();
        deque.add(new Point(x, y)); // 시작점 추가
        visited[x][y] = true; // 방문 표시
        unionNum[x][y] = unum; // 연합 번호 표시

        int sum = graph[x][y]; // 연합의 총 인구수
        int cnt = 1; // 연합을 이루는 나라의 개수

        // BFS 수행
        while (!deque.isEmpty()) {
            Point point = deque.poll(); // 큐에서 하나의 나라를 꺼내옴
            for (int d = 0; d < direction.length; d++) {
                int nx = point.x + direction[d][0];
                int ny = point.y + direction[d][1];

                // 범위 체크 및 방문하지 않은 인접한 나라인지 확인
                if (checkStatus(nx, ny)) {
                    // 국경선을 열 수 있는 조건인지 확인
                    if (checkRange(point.x, point.y, nx, ny)) {
                        sum += graph[nx][ny]; // 총 인구수 업데이트
                        cnt++; // 연합의 나라 개수 증가
                        visited[nx][ny] = true; // 방문