안전 영역

풀이

 먼저 graph에서 최소값과, 최대값을 찾는다. 최소값부터 최대값까지 for 문을 돌려서 DFS에 높이를 인자값으로 준다. 그리고 안전 영역 개수의 최대값을 구하면 된다. 여기서 안전 영역이란 DFS 인자값으로 주어진 높이보다 큰 지역을 뜻한다.

시간 복잡도 : O(N^3)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

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

public class Main {
    static int[][] graph;
    static int N;

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

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

    static void DFS(int t, boolean[][] visited, int x, int y){
        visited[x][y] = true;
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx && nx<N && 0<=ny && ny<N){
                if(visited[nx][ny]==false && graph[nx][ny]>t){
                    DFS(t, visited, nx, ny);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        int min_value = Integer.MAX_VALUE;
        int max_value = Integer.MIN_VALUE;
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                min_value = Math.min(min_value, graph[i][j]);
                max_value = Math.max(max_value, graph[i][j]);
            }
        }

        ArrayList<Integer> resultList = new ArrayList<>();
        for(int t=min_value; t<=max_value; t++){
            int result = 0;
            boolean[][]visited = new boolean[N][N];
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(graph[i][j]>t && visited[i][j]==false){
                        DFS(t, visited, i, j);
                        result++;
                    }
                }
            }
            resultList.add(result);
        }

        Collections.sort(resultList, Collections.reverseOrder());
        if(resultList.get(0)==0)
            bw.write(String.valueOf(1));
        else
            bw.write(String.valueOf(resultList.get(0)));
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

from collections import deque
N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

# 최대닶, 최소값 찾기
min_value = 101
max_value = 0
for i in graph:
    if max(i) > max_value:
        max_value = max(i)
    if min(i) < min_value:
        min_value = min(i)

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x,y,c,visited):
    visited[x][y] = True
    queue = deque([[x,y]])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visited[nx][ny] == False and graph[nx][ny] > c:
                    visited[nx][ny] = True
                    queue.append([nx,ny])


result = 0
for c in range(min_value, max_value+1):
    count = 0
    visited = [[False] * N for _ in range(N)]
    for x in range(N):
        for y in range(N):
            if visited[x][y] == False and graph[x][y] > c:
                bfs(x,y,c,visited)
                count += 1

    if count > result:
        result = count
if result == 0:
    print(1)
else:
    print(result)

시간복잡도 : O(n^3)