백준 온라인 저지 - 2468번: 안전영역

🔍 문제

---

 

2468번: 안전 영역

 

✏️ 풀이 - Java

---

 

높이가 될 수 있는 범위는 2에서 100사이이 므로 2에서 100까지 높이를 반복문으로 돌려주면서 안전한 영역의 개수를 세주었다.
지금까지 풀던 문제랑 비슷해서 어렵지 않게 풀 수 있었다. Codility에서 풀 때는 시간 제한이 엄격해서 이중 for문 쓰는 방식으로는 일단 포기했어야했는데 boj는 상대적으로 정답이라고 인정해주는 부분이 후한 것 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    int N; // 입력 N
    int a[][]; // 입력 배열
    int max = 1; // 출력할 결과값

    void input() throws IOException{ //입력 받는 메소드
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        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());
            }
        }

        br.close();
    }

    int[][] isSafety(int h) { //높이 h에 따라 잠기는 칸은 0 안전한 칸은 1로 return safe[][]
        int[][] safe = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(a[i][j] >= h) {
                    safe[i][j] = 1;
                } else {
                    safe[i][j] = 0;
                }
            }
        }
        return safe;
    }

    int zoneCnt(int[][] safe, boolean[][] visit) { //안전한 존 몇개인지 세기
        int cnt = 0;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(safe[i][j] == 1 && !visit[i][j]) { 
                    cnt++;
                    dfs(i, j, safe, visit);
                }
            }
        }

        return cnt;
    }

    void dfs(int n, int m, int[][] safe, boolean[][] visit) { //dfs
        if(n < 0 || n >= N || m < 0 || m >= N) return;
        if(visit[n][m]) return;
        if(safe[n][m] == 1 && !visit[n][m]) {
            visit[n][m] = true;
            dfs(n-1, m, safe, visit);
            dfs(n+1, m, safe, visit);
            dfs(n, m-1, safe, visit);
            dfs(n, m+1, safe, visit);
        }

    }

    void solve() {
        for(int i = 2; i <= 100; i++) {
            boolean visit[][] = new boolean[N][N]; // 방문체크 배열
            int[][] safe = isSafety(i); // 안전한지체크 배열
            int zoneCnt = zoneCnt(safe, visit);
            max = max < zoneCnt? zoneCnt : max;
        }

    }

    void print() throws IOException { //출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(max + "");
        bw.flush();
        bw.close();

    }

    public static void main(String args[]) throws IOException {
        Main main = new Main();
        main.input();
        main.solve();
        main.print();
    }

}