99클럽 코테 스터디 4일자 TIL [04/03]

참여 난이도

자바/미들러

오늘의 문제

백준 2468 안전 영역

 

 

문제 풀이

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

// 물에 잠기지 않는 안전한 영역
// 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];

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

        int start = 0;
        int save = 0;
        while(start < max) {
            boolean[][] arr2 = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j] > start) {
                        arr2[i][j] = true;
                    }
                }
            }

            int answer = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr2[i][j]) {
                        answer++;
                        dfs(arr2, i, j);
                    }
                }
            }

            if (answer > save) {
                save = answer;
            }
            start++;
        }
        System.out.println(save);
    }

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

    private static void dfs(boolean[][] arr2, int i, int j) {
        if (!arr2[i][j]) {
            return;
        }
        arr2[i][j] = false;

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

            if (nx >= 0 && nx < arr2.length && ny >= 0 && ny < arr2[0].length && arr2[nx][ny]) {
                dfs(arr2, nx, ny);
            }
        }
    }
}

• 과거에 많이 풀었었던 문제 유형(dfs)여서 금방 풀겠지라고 생각했습니다.
• 브루트포스 + dfs로 생각하여 풀이를 진행하였습니다.
• 높이가 정해지지 않았으니, 최댓값으로 조정하면 되었습니다.
• 높이는 1 ~100이하 while문은 100번 돌게 됩니다.
• 안에 for문은 boolean 이차원 배열로 침수되지 않은 지역을 true로 설정합니다.
• 두번째 for문은 boolean 이차원 배열이 true인 값들을 만나면 dfs를 돌리면서 침수되지 않은 지역들을 찾습니다.
• 이 answer값이 증가하게 되면서, 정답인 침수되지 않은 지역의 최댓값을 찾게 됩니다.

 

Tmi

감기 걸려서 요즘 힘드네요.

다들 건강 조심하시길~