백준 - 16234 인구 이동(Java)

dfs 문제입니다.

 

N*N 이차원 배열에서 네 방향으로 조건에 맞는 곳을 탐색해야 합니다.

• 조건 : 현재 위치와 다음 위치의 차이가 L 이상이고 R 이하여야 한다.(L과 R은 문제에 주어진다.)

 

문제 접근 순서는 다음과 같습니다.

1. dfs 탐색을 하여 국경을 연다.
2. 국경이 하나 이상 열리면 인구 재배치를 한다.
3. 국경이 더 이상 열리지 않을 때 까지 1, 2번을 반복한다.

 

※ [참고사항]

저의 경우 처음에 bfs로 구현을 했지만, 메모리 초과가 발생했습니다.

혹시나 하여 bfs가 아닌 dfs로 바꾸니 정답처리가 됐습니다.

bfs는 탐색 넓이, dfs는 탐색 깊이에 따라 메모리의 차이가 발생합니다.

일반적으로 dfs는 bfs보다 메모리에서 효율적이기 때문에,

메모리 초과가 발생하시는 분들은 dfs로 구현해 보시기 바랍니다.

 

[구현 코드]

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

public class Main {
    private static int n, l, r, sum;
    private static int[][] map;
    private static boolean[][] visited;
    private static List<Node> opens;
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    private static class Node{
        int x, y;

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

    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 stz = new StringTokenizer(br.readLine(), " ");

        int answer = 0;

        n  = Integer.parseInt(stz.nextToken());
        l  = Integer.parseInt(stz.nextToken());
        r  = Integer.parseInt(stz.nextToken());

        map = new int[n][n];

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

        opens = new ArrayList<>();
        boolean isGoing;
        while (true) {
            isGoing = false;
            visited = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j]) {
                        opens.clear();

                        sum = 0;
                        dfs(i, j, opens);
                        if(opens.size() > 1){ // 문이 열렸다면
                            isGoing = true;
                            for (Node node : opens) {
                                map[node.x][node.y] = (int)Math.floor((double) sum / opens.size());
                            }
                        }
                    }
                }
            }
            if(isGoing) answer++;
            else break;
        }

        bw.write(String.valueOf(answer));

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

    private static void dfs(int x, int y, List<Node> opens){
        visited[x][y] = true;
        sum += map[x][y];
        opens.add(new Node(x, y));

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(!(nx>=0 && ny>=0 && nx<n && ny<n)) continue;
            if(visited[nx][ny]) continue;

            int sub = Math.abs(map[x][y] - map[nx][ny]);

            if(sub >= l && sub <= r) {
                dfs(nx, ny, opens);
            }
        }
    }
}