[백준 16234번] 인구 이동

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

 

package implement;

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

public class Impl16234 {
    static int N;

    static int L;
    static int R;

    static int[][] map;

    static int result = 0;

    // visit가 true일때 탐색 불가 왜냐하면 동시에 돌아서 데이터 정합성 깨짐 1일마다 갱신됨 대신


    // wall에서 담아서 탐색하기

    static boolean resultFlag;

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    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());
            }
        }

        countDay();
        System.out.println(result);
    }

    private static void countDay() {

        while (true) {
            resultFlag = false;
            boolean[][] visit = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visit[i][j]) {
                        slove(i, j, visit);
                    }
                }
            }

            if (!resultFlag) {
                break;
            }

            result++;
        }

    }

    private static void slove(int x, int y, boolean[][] visit) {
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> wall = new ArrayList<>();
        visit[x][y] = true;
        wall.add(new int[]{x, y});
        queue.add(new int[]{x, y});
        int cnt = 1;
        int sum = map[x][y];
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int sX = temp[0];
            int sY = temp[1];

            for (int i = 0; i < 4; i++) {
                int nextX = sX + dx[i];
                int nextY = sY + dy[i];
                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) {
                    continue;
                }
                if (visit[nextX][nextY]) {
                    continue;
                }
                int substance = Math.abs(map[sX][sY] - map[nextX][nextY]);
                if (substance >= L && substance <= R) {
                    resultFlag = true;
                    visit[nextX][nextY] = true;
                    cnt++;
                    sum += map[nextX][nextY];
                    queue.add(new int[]{nextX, nextY});
                    wall.add(new int[]{nextX, nextY});
                }
            }
        }

        int value = sum / cnt;

        for (int[] pos : wall) {
            map[pos[0]][pos[1]] = value;
        }

    }

}

 

핵심은 왼쪽에 벽이 있어도 다른 방향에서 벽이 없다면 해당 좌표를 wall 리스트에 넣어 계산해주면 된다는 것이다.
visit 배열은 하루마다 초기화되며, 이는 동시에 돌 때 데이터 정합성을 보장하기 위해 사용된다.

초반에 wall을 boolean 배열로 뒀더니 매번 새로 만들어야 해서 시간초과가 났다. 배열은 new boolean[N][N]로 매번 새로 할당되면서 메모리 할당 비용이 크기 때문에 시간초과가 발생한 것이다. 그래서 List로 관리해 효율성을 높였다.

문제 자체는 어렵지 않았지만, 시간이 좀 많이 걸렸다. 더 단축하고 연습해야겠다.