C++ 방식으로 푼 안전영역

백준 2468 안전영역 (BFS): 알고리즘 공부
+) 19년도 8월 A형에 비슷한 문제가 출제됐다고 한다. 단지 번호 구하기와 비슷하게 풀면 되는 것 같다. 처음에 문제가 이해가 되지 않아서 각각의 경우의 수로 나눠 보았다. 비가 지역 2만큼 온다면, 안전한 영역은 +로 탐색할 경우, 하나로 볼 수 있다. 침수 지역이 3일 경우에는 4영역으로 나눠짐을 볼 수 있다. 비가 5만큼 온다면, 기존의 6-4-6 영역이 둘로 쪼개져 영역이 5군데가 된다.
알고리즘 공부




DFS 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int[][] map;
    public static int[][] check;
    public static int N;

    public static int[] dr = { 1, 0, -1, 0 };
    public static int[] dc = { 0, 1, 0, -1 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        check = new int[N][N];
        int maxday = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (maxday < map[i][j])
                    maxday = map[i][j];
            }
        } // INIT END
        int ans = 0, max = 0;
        for (int n = 0; n <= maxday; n++) {
            ans = sol(n);
            if (max < ans) {
                max = ans;
            }
        }
        System.out.println(max);

        br.close();
    }// Main End

    public static int sol(int day) {
        check = new int[N][N];
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > day && check[i][j] == 0) {
                    check[i][j] = ++cnt;
                    dfs(day, i, j);
                }
            }
        }
        return cnt;
    }

    public static void dfs(int day, int r, int c) {
        for (int d = 0; d < dr.length; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (isIn(nr, nc) && map[nr][nc] > day && check[nr][nc] == 0) {
                check[nr][nc] = check[r][c];
                dfs(day, nr, nc);
            }
        }
    }

    public static boolean isIn(int r, int c) {
        return (0 <= r && r < N && 0 <= c && c < N);
    }
}



BFS방식

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int[][] map;
    public static int[][] check;
    public static int N;
    public static Queue<Point> q = new LinkedList<Point>();;
    public static int[] dr = { 1, 0, -1, 0 };
    public static int[] dc = { 0, 1, 0, -1 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        int maxday = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (maxday < map[i][j])
                    maxday = map[i][j];
            }
        } // INIT END
        int max = 0;
        for (int n = 0; n <= maxday; n++) {
            check = new int[N][N];
            int ans = sol(n);
            if (max < ans) {
                max = ans;
            }

        }

        System.out.println(max);

        br.close();
    }// Main End

    public static int sol(int day) {
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > day && check[i][j] == 0) {
                    check[i][j] = ++cnt;
                    q.offer(new Point(i, j));
                }
                while (!q.isEmpty()) {
                    int r = q.peek().x;
                    int c = q.poll().y;

                    for (int d = 0; d < dr.length; d++) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];

                        if (isIn(nr, nc) && map[nr][nc] > day && check[nr][nc] == 0) {
                            check[nr][nc] = check[r][c];
                            q.offer(new Point(nr, nc));
                        }
                    }

                } // END WHILE LOOP

            }
        }

        return cnt;
    }

    public static boolean isIn(int r, int c) {
        return (0 <= r && r < N && 0 <= c && c < N);
    }
}

왈독님의 창작활동을 응원하고 싶으세요?