[Silver I] 안전 영역 - 2468

성능 요약

메모리: 18764 KB, 시간: 220 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 28일 17:45:04

문제 설명

<p>재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.</p>

<p>어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.</p>

<p>물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). </p>

<p>또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. </p>

<p>어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. </p>

입력

출력

풀이

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

public class Main {
    static int N,result, count, nx, ny;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Integer> heights = new ArrayList<>();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        
        for (int i=0; i<N; i++) {
            st= new StringTokenizer(br.readLine(), " ");
            for (int j= 0; j < N; j++) {
                graph[i][j]= Integer.parseInt(st.nextToken());
                if (!heights.contains(graph[i][j])) { // 건물 높이 리스트
                    heights.add(graph[i][j]);
                }
            }
        }

        result= 1;
        
        for (Integer height : heights) {
            count= 0;
            visited= new boolean[N][N];
            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    if (!visited[i][j] && graph[i][j] >= height) {
                        count++;
                        dfs(height, i, j);
                    }
                }
            }
            result = Math.max(result, count);
        }
        System.out.println(result);
    }

    // dfs
    static void dfs(int height, int x, int y) {
        visited[x][y] = true;
        for (int i=0; i<4; i++) {
            nx= x + dx[i];
            ny= y + dy[i];
            if (nx>=0 && ny>=0 && nx<N && ny<N) {
                if (!visited[nx][ny]) {
                    if (graph[nx][ny] >= height) { // 해당 건물 > 물의 높이
                        dfs(height, nx, ny);
                    }
                }
            }
        }
    }
}

[Silver I] 안전 영역 - 2468

성능 요약

분류

제출 일자

문제 설명

입력

출력

풀이

댓글