[99클럽 코테 스터디 4일차 TIL] 안전 영역

 

4일차 문제

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

 

 

 

문제 풀이

 

높이가 4 이하인 지점이 물에 잠긴 경우, 잠기지 않은 안전한 영역의 개수는 5

 

높이가 6 이하인 지점이 물에 잠긴 경우, 잠기지 않은 안전한 영역의 개수는 4

...

위의 과정을 반복하며 물에 잠기지 않은 안전한 영역의 최대 개수를 구하는 문제

 

 

 

BFS와 DFS를 활용하여 풀이하였다.

 

1) 배열의 값을 입력받으며 최대 값 max를 저장해준다. -> 물에 잠길 수 있는 높이의 최대값

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

 

 

2) 1~max 값을 돌며 BFS나 DFS를 수행해주고 각 depth 마다 안전한 영역의 최대값을 구해준다.

* BFS, DFS : 물에 잠기지 않는 영역 순회

for(int depth=1; depth<=max; depth++) {
    visited = new boolean[N][N];
    int area = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(!visited[i][j] && arr[i][j] >= depth) {
                area++;
                // BFS(i, j, depth);
                DFS(i, j, depth);
            }
        }
    }

    answer = Math.max(answer, area);
}

---

1. BFS

private static void BFS(int x, int y, int depth) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] {x, y});
        visited[x][y] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int i=0; i<4; i++) {
                int nextX = now[0] + dx[i];
                int nextY = now[1] + dy[i];

                if(nextX>=0 && nextX<N && nextY>=0 && nextY<N) {
                    if(!visited[nextX][nextY] && arr[nextX][nextY] >= depth) {
                        q.add(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }

 

2. DFS

private static void DFS(int x, int y, int depth) {
        visited[x][y] = true;

        for(int i=0; i<4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX>=0 && nextX<N && nextY>=0 && nextY<N) {
                if(arr[nextX][nextY] >= depth && !visited[nextX][nextY]) {
                    DFS(nextX, nextY, depth);
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

 

 

 

최종 코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        arr = new int[N][N];

        int answer = 0;

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

        for(int depth=1; depth<=max; depth++) {
            visited = new boolean[N][N];
            int area = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(!visited[i][j] && arr[i][j] >= depth) {
                        area++;
                        // BFS(i, j, depth);
                        DFS(i, j, depth);
                    }
                }
            }

            answer = Math.max(answer, area);
        }
        System.out.println(answer);
    }

    private static void DFS(int x, int y, int depth) {
        visited[x][y] = true;

        for(int i=0; i<4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX>=0 && nextX<N && nextY>=0 && nextY<N) {
                if(arr[nextX][nextY] >= depth && !visited[nextX][nextY]) {
                    DFS(nextX, nextY, depth);
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

    private static void BFS(int x, int y, int depth) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] {x, y});
        visited[x][y] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int i=0; i<4; i++) {
                int nextX = now[0] + dx[i];
                int nextY = now[1] + dy[i];

                if(nextX>=0 && nextX<N && nextY>=0 && nextY<N) {
                    if(!visited[nextX][nextY] && arr[nextX][nextY] >= depth) {
                        q.add(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
}