8회차 스터디

8월 둘재주[8회차]

주제 : 그래프이론

 

내 문제 : 안전영역_2468

위 와같은 과정을 거쳐 나눠진 영역의 최대값을 구한다. 

 

풀이 방법

가장 낮은 높이를 구하고

그 높이를 모두 물에 잠기게 표시한다.

그리고 전체를 순회하면서 나뉘어진 구역의 개수를 센다.

구역의 최대갯수를 비교하여 갱신한다. 

 

그리고 그 다음 높이를 물에 잠기게 표시하고

마찬가지로 전체를 순회하면서 나뉘어진 구역의 개수를 센다.

구역의 최대갯수를 비교하여 갱신한다.

 

이러한 과정을 반복하여 가장 높은 높이까지 다 구하면

구역의 최대 갯수가 나오게 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 안전영역_2468 {
    static int N;
    static int[][] all;
    static int[] height;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        // 모든 영역
        all = new int[N][N];
        // 다른 높이들이 담긴 배열
        height = new int[101];
        // 가장 처음 변동이 있는 높이
        int min = 100;
        // 나눠진 구역 수
        int cnt = 1;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                int X = Integer.parseInt(st.nextToken());
                all[i][j] = X;
                height[X] = 1;
                min = Math.min(min, X);
            }
        }
        cnt = Math.max(cnt, pull(min));
        for (int i = min; i < height.length; i++) {
            if (height[i] != 0) {
                cnt = Math.max(cnt, pull(i));
            }
        }
        System.out.println(cnt);

    }

    // 해당 높이를 모두 침수시키는 함수
    public static int pull(int A) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
            // 침수된 곳은 0으로 표시
                if (all[i][j] == A) all[i][j] = 0;
            }
        }
        return dfs();
    }

    // 구역 갯수 구하는 함수
    public static int bfs() {
        int[] dy = new int[]{1, -1, 0, 0};
        int[] dx = new int[]{0, 0, 1, -1};
        int result = 0;
        int[][] visited = new int[all.length][all.length];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (all[i][j] == 0 || visited[i][j] == 1) continue;
                visited[i][j] = 1;
                result++;
                q.add(new int[]{i, j});

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int cy = cur[0];
                    int cx = cur[1];
                    for (int k = 0; k < 4; k++) {
                        int ny = cy + dy[k];
                        int nx = cx + dx[k];
                        if (ny >= all.length || ny < 0 || nx >= all.length || nx < 0) continue;
                        if (visited[ny][nx] == 1) continue;
                        if (all[ny][nx] != 0) {
                            visited[ny][nx] = 1;
                            q.add(new int[]{ny, nx});
                        }
                    }

                }
            }
        }
        return result;
    }
}