[백준 2468] 안전 영역(Java)

[백준 2468] 안전 영역(Java)

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

2468번: 안전 영역

 

해결 방법

1트

문제를 보고 DFS또는 BFS로 해결하면 좋을 거라고 판단했습니다.
저는 DFS를 사용했습니다.

시작 지점에서 DFS가 종료될때 마다 count를 증가시키면 된다고 생각했습니다.^^

그런데….
틀렸습니다.

 

2트

문제를 다시 읽어보니 최대 안전 영역을 구하라고 했습니다.
저는 n을 기준으로 안전영역을 구하는 것인지 알았습니다..😭

따라서 지역에서 최대높이를 구하고 그 만큼 loop를 통해 DFS를 수행 합니다.👍

풀이

public class Quiz2468zmfha ap {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 인접 행렬 생성
        int max = Integer.MIN_VALUE;
        int[][] map = new int[n][n];
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(max, map[i][j]);
            }
        }


        int count = 0;
        int maxCount = Integer.MIN_VALUE;
        for(int k = 0; k <= max; k++) {
            boolean[][] visited = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && map[i][j] > k) {
                        dfs(map, visited, i, j, k);
                        count++;
                    }
                }
            }
            // 안전영역 최대 갯수 계산
            maxCount = Math.max(count, maxCount);
            count = 0;
        }

        System.out.print(maxCount);
        br.close();
    }

    private static void dfs(int[][] map, boolean[][] visited, int x, int y, int k) {

        int[] ud = {1, -1, 0, 0};
        int[] lr = {0, 0, 1, -1};
        for(int i = 0; i < 4; i++) {
            int newX = x + ud[i];
            int newY = y + lr[i];

            // 범위 체크
            if(newX < 0 || newY < 0 || newX >= n || newY >= n) {
                continue;
            }

            if(!visited[newX][newY] && map[newX][newY] > k) {
                visited[newX][newY] = true;
                dfs(map, visited, newX, newY, k);
            }
        }
    }
}

 

그런데… 메모리를 보니…?
메모리 소비를 너무 많이 하네요…

풀이(메모리 고려)

public class Quiz2468 {
    static int n;
    static int[][] map;
    static boolean[][] visited;

    // 이 녀석을 static으로 하지 않으면
    // dfs를 수행할때 마다 신규로 메모리를 할당한다.
    static int[] ud = {1, -1, 0, 0};
    static int[] lr = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 인접 행렬 생성
        int max = Integer.MIN_VALUE;
        map = new int[n][n];
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 지역의 최대 높이
                max = Math.max(max, map[i][j]);
            }
        }


        // 안전지역 카운트
        int count = 0;
        int maxCount = Integer.MIN_VALUE;
        // 지역의 최대 높이 만큼 dfs 수행
        for(int k = 0; k <= max; k++) {
            visited = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && map[i][j] > k) {
                        dfs(i, j, k);
                        // 안전지역 카운트 증가
                        count++;
                    }
                }
            }
            // 안전영역 최대 갯수 계산
            maxCount = Math.max(count, maxCount);
            // 안전지역 카운트 초기화
            count = 0;
        }

        System.out.print(maxCount);
        br.close();
    }

    private static void dfs(int x, int y, int k) {
        for(int i = 0; i < 4; i++) {
            // 상, 하, 좌, 우 이동
            int newX = x + ud[i];
            int newY = y + lr[i];

            // 범위 체크
            if(newX < 0 || newY < 0 || newX >= n || newY >= n) {
                continue;
            }

            if(!visited[newX][newY] && map[newX][newY] > k) {
                visited[newX][newY] = true;
                dfs(newX, newY, k);
            }
        }
    }
}

 

와.... 메모리가 약 50,000KB가 줄었습니다!!! 👍