[BOJ] 2468번 : 안정영역 (JAVA)

간만에 알고리즘 타임

저번에 풀었던 문제인데 그냥 복습할 겸 다시 풀어봤는디 저번이랑 풀이가 다르다. 신기한 내 머릿속

https://www.acmicpc.net/problem/2468

 

정말 간단한 문제다. 

높이를 확인해서 해당 높이보다 큰 지점은 안정영역이다. 해당 지점의 영역 개수의 최대를 구하는 문제.

 

1. 우선 dfs를 활용한다. (보통 저렇게 영역을 구하는 문제는 dfs를 활용하는 것이 좋다. 연결된 부분을 다 체크하고 돌아오기 땜시) 

// 안전한 영역의 최대 개수
static void dfs(int x, int y, int n) {
    visited[x][y] = true;

    for(int i=0;i<4;i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]) {
            if(map[nx][ny]>n) {
                visited[nx][ny]=true;
                dfs(nx, ny, n);
            }
        }
    }
}

 

함수에서 n은 영역의 높이이다. 함수를 호출할 때 영역의 높이를 넘겨주고, 방문을 안했던 곳 + 해당 map의 높이가 n보다 크다면 그때 방문처리를 해주면서 다시 함수를 호출한다.

 

dfs를 main에서 호출할 때느 아래처럼 n이 1부터 100까지길래 그냥 계속 돌렸다. 근데 다시 생각해보면 그냥 처음에 함수 입력받을 때 가장 큰 값을 구하고 그 값까지만 돌려도 됐을 문제였다. 쨋든, 아래처럼 각 영역의 개수를 구하고 최대값을 구해준다. 

for(int n=1;n<=100;n++) {
    cnt=0;
    visited = new boolean[N][N];
    for(int i=0;i<N;i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j] && map[i][j] > n) {
                cnt++;
                dfs(i, j, n);
            }
        }
    }
    Max = Math.max(Max, cnt);
}

 

근데 이것만 해서 바로 Max 값을 출력하면 66%정도에서 틀렸다고 나온다. 이걸 체크 안해줬기 때문. 코드만 보면 만약 아무 지역이 물에 잠기지 않는다면 그냥 0이 출력되는 구조이다. 

// 아무 지역도 물에 잠기지 않으면 안정 영역의 최대 개수는 1
if(Max!=0) System.out.println(Max);
else System.out.println(1);

 

그치만 아무 지역도 물에 잠기지 않으면 영역의 최대 개수는 1이다. 그래서 조건문을 추가해줬더니! 통과! 

 

[전체 코드]

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

public class Main {
    static int N;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static int[][] map;
    static int Max;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        Max = -1;

        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int cnt=0;
        for(int n=1;n<=100;n++) {
            cnt=0;
            visited = new boolean[N][N];
            for(int i=0;i<N;i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && map[i][j] > n) {
                        cnt++;
                        dfs(i, j, n);
                    }
                }
            }
            Max = Math.max(Max, cnt);
        }

        // 아무 지역도 물에 잠기지 않으면 안정 영역의 최대 개수는 1
        if(Max!=0) System.out.println(Max);
        else System.out.println(1);

    }

    // 안전한 영역의 최대 개수
    static void dfs(int x, int y, int n) {
        visited[x][y] = true;

        for(int i=0;i<4;i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]) {
                if(map[nx][ny]>n) {
                    visited[nx][ny]=true;
                    dfs(nx, ny, n);
                }
            }
        }
    }
}