[백준] 16234번 / Java / 인구 이동

문제 - (https://www.acmicpc.net/problem/16234)

크게 어려웠던 문제는 아니다.

문제를 다 풀고 다른 코드들을 확인해보니 BFS로 많이 풀었지만 나는 DFS가 더 편해서 DFS로 풀었다.

DFS + 시뮬레이션 문제였다.

 

문제를 풀다가 개인적으로 뿌듯한 구현이 있었다. 바로 이부분!!

	// 같은 연합끼리 인구 이동 시작
            int[] unions = new int[check];
            int[] unionsCnt = new int[check];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] == 0) continue;
                    unions[visited[i][j]] += map[i][j];
                    unionsCnt[visited[i][j]]++;
                }
            }

            // 인구 이동 결과로 map 업데이트
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] == 0) continue;
                    map[i][j] = unions[visited[i][j]] / unionsCnt[visited[i][j]];
                }
            }

첫 dfs를 수행할 때, int형 배열인 visited에 연합인 국가들을 check로 표시했다.

그 다음 번 dfs는 check++를 한 채로 visited를 채웠다.

이렇게하면 연합국인 좌표들은 같은 숫자로 visited에 채워져 있을 것이다.

 

• unions 배열의 인덱스는 연합국 이름이고, 값에는 연합국들이 가지고 있던 고유 인구의 수를 합한 것을 넣었다.
• unionsCnt 배열의 인덱스도 연합국 이름이고, 값에는 연합국의 수를 넣었다. ( 문제에서 요구하는 구현을 따라 unions/unionsCnt 해주기 위해 )

따라서 unions[visited[i][j]] += map[i][j];

이 부분은 이렇게 해석할 수 있다

=> "visited[i][j] = 연합국 이름"을 "unions의 인덱스로 사용"

unions[1] = 1 연합국 인구 수의 합

unionsCnt[1] = 1 연합국의 수

 

---

📌주의할 점

• 다시 DFS를 수행하려고 할 땐, 초기값들을 다시 초기화해주는 과정을 잊지 말 것!!

---

😅실수

• 방문하지 않았던 (연합국이 아닌)좌표는 map을 업데이트하는 과정에서 제외시켜야 하는데 그렇게 안해서 틀렸었다 ㅠㅠ
  이런 사소한 실수 때문에 디버깅을 돌리는 시간이 없도록 메인 로직을 모두 구현했더라도 초심을 잃지 않고 세세한 조건을 고려하면서 짜야겠다.

 

---

코드

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

/**
 * 1시간 12분
 */
public class Migration {
    static int n;
    static int L;
    static int R;
    static int[][] map;
    static int[][] visited;
    // 상 좌 우 하
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    static int check = 1;
    static int answer;

    static void dfs(int y, int x) {
        // 기저 : 범위를 벗어나면 종료
        if (y < 0 || x < 0 || y >= n || x >= n) return;

        // 현재 좌표에서 국경선 열 수 있는 곳 확인
        for (int move = 0; move <= 3; move++) {
            int moveY = y + dy[move];
            int moveX = x + dx[move];

            if (moveY < 0 || moveX < 0 || moveY >= n || moveX >= n) continue;

            int diff = Math.abs(map[y][x] - map[moveY][moveX]);
            if (diff >= L && diff <= R) {
                // 국경선 열 수 있는 국가 찾음
                visited[y][x] = check;
                if (visited[moveY][moveX] != 0) continue;
                dfs(moveY, moveX);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        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());
            }
        }

        while (true) {
            boolean breakFlag = true;
            int zeroCnt = 0;
            check = 1;
            visited = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] != 0) continue;
                    dfs(i, j);
                    check++;
                    breakFlag = false;
                    zeroCnt++;
                }
            }
            if (breakFlag) break;
            // dfs 수행했음에도 visited가 모두 0이면 인구이동이 없던 것이므로 반복문 종료
            if (zeroCnt == n * n) break;
            answer++;

            // 같은 연합끼리 인구 이동 시작
            int[] unions = new int[check];
            int[] unionsCnt = new int[check];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] == 0) continue;
                    unions[visited[i][j]] += map[i][j];
                    unionsCnt[visited[i][j]]++;
                }
            }

            // 인구 이동 결과로 map 업데이트
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] == 0) continue;
                    map[i][j] = unions[visited[i][j]] / unionsCnt[visited[i][j]];
                }
            }
        }

        System.out.println(answer);
        br.close();
    }
}