[規格]2468セキュリティエリア(Java)

質問リンク

もんだいぶんせき

エリア:上下左右に接続されています.上下左右接続なら同じ領域です.

上記の場合,領域の個数は5個である.

入力

しゅつりょく

に答える

private static int countRegion(int height) {
    int count = 0;
    
    //물에 잠김 or 방문한 영역을 표시할 ch 배열
    boolean[][] ch = new boolean[n][n];

				//물에 잠긴 영역 표시
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(map[i][j]<=height)
                ch[i][j] = true;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
        	//방문하지 않은 지역이 있다면
            if(ch[i][j]==false){
                count++; //개수 추가
                DFS(i, j, ch); //연결된 부분 체크 
            }
        }

    return count;
}

private static void DFS(int r, int c, boolean[][] ch) {
	//상하좌우로 탐색한다.
    for(int i=0; i<4; i++){
        int nr = r+ dr[i];
        int nc = c+dc[i];

        if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
        if(ch[nr][nc]==false){
            ch[nr][nc]= true;
            DFS(nr, nc, ch);
        }
    }
}

完全なコード

import java.util.*;

public class Main {
    //상하좌우 탐색에 사용할 변위
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    static int n;
    static int[][] map;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        map = new int[n][n];
        int maxHeight = Integer.MIN_VALUE;
        int answer = Integer.MIN_VALUE;

        //지도를 입력 받으며 최대 높이 갱신
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = scanner.nextInt();
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }

        //0 ~ maxHeight 동안 안전 영역의 개수를 센다.
        for(int i=0; i<=maxHeight; i++){
            //안전 영역의 최대 개수 갱신
            answer = Math.max(countRegion(i), answer);
        }
        System.out.println(answer);
    }

    private static int countRegion(int height) {
        int count = 0;

        //물에 잠김 or 방문한 영역을 표시할 ch 배열
        boolean[][] ch = new boolean[n][n];

        //물에 잠긴 영역 표시
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(map[i][j]<=height)
                    ch[i][j] = true;

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++){
                //방문하지 않은 지역이 있다면
                if(ch[i][j]==false){
                    count++; //개수 추가
                    DFS(i, j, ch); //연결된 부분 체크
                }
            }

        return count;
    }

    private static void DFS(int r, int c, boolean[][] ch) {
        //상하좌우로 탐색한다.
        for(int i=0; i<4; i++){
            int nr = r+ dr[i];
            int nc = c+dc[i];

            if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
            if(ch[nr][nc]==false){
                ch[nr][nc]= true;
                DFS(nr, nc, ch);
            }
        }
    }
}