16234번: 인구 이동

문제

N×N 크기의 땅이 있고, 각 땅에는 나라가 하나씩 존재하며 각 나라에는 인구수가 주어집니다. 인접한 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라가 공유하는 국경선을 하루 동안 엽니다. 국경선이 열려 서로 이동할 수 있는 나라들을 '연합'이라고 하며, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. (소수점은 버림) 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.

• 입력: 첫째 줄에 N, L, R이 주어지고, 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어집니다.
• 출력: 인구 이동이 발생하는 일수(방문 횟수)를 출력합니다.

링크: https://www.acmicpc.net/problem/16234

풀이: DFS 탐색을 통한 연합 구성 시뮬레이션

이 문제는 더 이상 인구 이동이 발생하지 않을 때까지 전체 맵을 계속해서 탐색해야 하는 시뮬레이션 문제입니다.

1. 시뮬레이션 반복 (while 루프): 며칠 동안 인구 이동이 일어날지 알 수 없으므로 while (true) 루프를 돌며 하루 단위의 시뮬레이션을 진행합니다. 매일 탐색을 시작하기 전 방문 배열(visited)을 초기화하고, 인구 이동 발생 여부를 체크할 플래그(flag)를 false로 둡니다.
2. 연합 찾기 (DFS): 맵 전체를 순회하며 아직 방문하지 않은 나라(!visited[i][j])를 발견하면 DFS 탐색을 시작합니다.
   • dfs 함수는 상하좌우를 탐색하며, 인접한 두 나라의 인구 차이가 L 이상 R 이하일 때만 재귀적으로 탐색을 이어나갑니다.
   • 탐색 과정에서 방문한 나라들은 연합에 속하므로 list에 좌표를 저장하고, 그 나라들의 인구수를 모두 합산하여 반환(ret)합니다.
3. 인구 분배 및 맵 갱신: DFS 탐색이 끝난 후 구성된 연합의 크기(list.size())가 1보다 크다면, 인구 이동이 발생한 것입니다.
   • 인구 이동이 발생했음을 기록(flag = true)합니다.
   • (연합의 총 인구수) / (연합의 나라 수)를 계산하여, list에 저장해둔 연합 국가들의 좌표 위치에 새로운 인구수를 덮어씁니다.
4. 종료 조건: 전체 맵을 다 돌았는데도 연합이 단 하나도 구성되지 않았다면(!flag), 더 이상 인구 이동이 불가능한 상태이므로 루프를 탈출(break)하고, 지금까지 누적된 날짜(ans)를 출력합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, l, r, ans;
    static int[][] a;
    static boolean[][] visited;
    
    // 현재 구성 중인 연합의 좌표를 담을 리스트
    static List<Node> list;
    
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       l = Integer.parseInt(st.nextToken());
       r = Integer.parseInt(st.nextToken());

       a = new int[n][n];
       for (int i = 0; i < n; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             a[i][j] = Integer.parseInt(st.nextToken());
          }
       }

       // 1. 인구 이동이 없을 때까지 반복
       while (true) {
          boolean flag = false; // 오늘 하루 인구 이동이 일어났는지 확인
          visited = new boolean[n][n];
          
          // 2. 전체 맵을 순회하며 연합 찾기
          for (int i = 0; i < n; i++) {
             for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                   list = new ArrayList<>();
                   // DFS를 통해 연합의 총 인구수를 구함
                   int sum = dfs(i, j);
                   
                   // 연합에 속한 나라가 2개 이상이라면 인구 이동 수행
                   if (list.size() != 1) {
                      flag = true;
                      int tmp = sum / list.size(); // 분배될 인구수
                      
                      // 연합을 이루는 각 칸에 새로운 인구수 갱신
                      for (Node node : list) {
                         a[node.y][node.x] = tmp;
                      }
                   }
                }
             }
          }

          // 인구 이동이 단 한 번도 일어나지 않았다면 시뮬레이션 종료
          if (!flag)
             break;

          // 하루 경과
          ans++;
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }

    // 연합을 찾고 인구수 합을 반환하는 DFS 메서드
    static int dfs(int y, int x) {
       visited[y][x] = true;
       int ret = a[y][x];
       list.add(new Node(y, x)); // 현재 좌표를 연합 리스트에 추가
       
       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          if (ny < 0 || nx < 0 || ny >= n || nx >= n)
             continue;
             
          // 이미 방문한 곳이거나, 인구 차이가 L~R 범위를 벗어난다면 무시
          int diff = Math.abs(a[y][x] - a[ny][nx]);
          if (visited[ny][nx] || diff < l || diff > r)
             continue;
             
          ret += dfs(ny, nx);
       }

       return ret;
    }

    static class Node {
       int y, x;

       Node(int y, int x) {
          this.y = y;
          this.x = x;
       }
    }
}

알고리즘 분류

그래프 탐색, 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS), 시뮬레이션