[백준] 2468 안전영역

문제 및 입출력

문제 접근

처음 문제를 접근 하였을 때는 총 3가지 단계로 분류하여 문제를 풀이하였다.

1. 입력 받은 배열을 bfs 순회하며 안전 영역 표시
2. 안전 영역을 표시한 배열을 순회
3. 잠기지 않은 영역을 순회할 때마다 bfs로 순회하고 횟수 카운트

영역의 높이 만큼 저 3단계를 반복하며 카운트 한 숫자 중, 맥시멈인 숫자가 이 문제의 답이 되는 것이다.

이후 풀이를 제출한 결과 풀이는 성공하였다(사실 맞았다고 해줄 지 몰랐다 ㅋㅋ)

코드 길이가 상당히 길었고, 성공은 했지만 메모리나 시간적인 측면에서 비효율적이라는 생각이 들었다.

그래서 다시 생각해본 결과, 3단계에서 굳이 안전 영역을 표시할 필요가 없음을 느꼈다. 왜냐하면, 방문하지 않은 영역 중 물의 높이보다 높은 영역을 순회한다고 생각하면 기존의 1, 2 단계를 한 번에 구현이 가능했기 때문이다.

이를 바탕으로 다시 구현한 결과 메모리와 시간을 절약하며 성공한 풀이를 다시 구현할 수 있었다.

구현 코드

1차 시도

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

class Reg {
    int x;
    int y;

    Reg(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int N;
    static int max = 0;
    static Integer[][] reg;
    static boolean[][] check;
    static boolean[][] got;
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    static int solve() {
        int count = 0;

        for (int i = 0; i < max; i++) {
            check = new boolean[N][N];
            got = new boolean[N][N];

            bfs(i);

            count = find_max(count);
        }

        return count;
    }

    static void bfs(int i) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(0, 0));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

            for (int j = 0; j < 4; j++) {
                int x = temp.x + dx[j];
                int y = temp.y + dy[j];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!got[x][y]) {
                        if (reg[x][y] <= i) {
                            check[x][y] = true;
                        }
                        q.add(new Reg(x, y));
                        got[x][y] = true;
                    }
                }
            }
        }
    }

    static int find_max(int count) {
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!check[i][j]) {
                    check_true(i, j);
                    result++;
                }
            }
        }
        return Math.max(count, result);
    }

    static void check_true(int tx, int ty) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(tx, ty));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

            for (int j = 0; j < 4; j++) {
                int x = temp.x + dx[j];
                int y = temp.y + dy[j];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!check[x][y]) {
                        check[x][y] = true;
                        q.add(new Reg(x, y));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        reg = new Integer[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while (st.hasMoreTokens()) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp > max)
                    max = temp;
                reg[i][j] = temp;
                j++;
            }
        }

        System.out.println(solve());
    }
}

2차 시도

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

class Reg {
    int x;
    int y;

    Reg(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class bj2468 {
    static int N;
    static Integer[][] reg;
    static boolean[][] check;
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    static void dfs(int tx, int ty, int depth) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(tx, ty));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

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

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!check[x][y] && reg[x][y] > depth) {
                        q.add(new Reg(x, y));
                        check[x][y] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        reg = new Integer[N][N];

        int max = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while (st.hasMoreTokens()) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp > max)
                    max = temp;
                reg[i][j] = temp;
                j++;
            }
        }

        int result = 0;
        for (int depth = 0; depth < max; depth++) {
            check = new boolean[N][N];
            int count = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!check[i][j] && reg[i][j] > depth) {
                        dfs(i, j, depth);
                        count++;
                    }
                }
            }
            result = Math.max(count, result);
        }

        System.out.println(result);
    }
}