백준 2468 - 안전 영역

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        int n;
        int table[][] = new int[102][102];
        //int visited[][] = new int[102][102];
        List<Integer> dir_x = List.of(0, 1, 0, -1);
        List<Integer> dir_y = List.of(1, 0, -1, 0);

        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.nextLine());
        int max_height = 0;
        int min_height = 102;

        for (int i = 0; i < n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(scanner.nextLine());
            for (int j = 0; j < n; j++) {
                table[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                if (table[i][j] > max_height) {
                    max_height = table[i][j];
                }
                if (table[i][j] < min_height) {
                    min_height = table[i][j];
                }

            }
        }

        int max_val = 1;
        for (int height = min_height; height < max_height; height++) {

            int[][] visited = new int[102][102];
            int cnt = 0;
            Queue<Pair> q = new LinkedList<>();

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (table[i][j] - height > 0 && visited[i][j] == 0) {
                        q.add(new Pair(i,j));
                        visited[i][j] = 1;
                        cnt++;

                        while (!q.isEmpty()) {
                            Pair cur = q.peek();
                            q.remove();
                            //cnt++;
                            for (int dir = 0; dir < 4; dir++) {
                                int c_x = cur.x + dir_x.get(dir);
                                int c_y = cur.y + dir_y.get(dir);
                                if (c_x < 0 || c_x >= n || c_y < 0 || c_y >= n) continue;
                                if (table[c_x][c_y] - height <= 0 || visited[c_x][c_y] == 1) continue;
                                visited[c_x][c_y] = 1;
                                q.add(new Pair(c_x, c_y));
                            }
                        }
                    }
                }
            }
            if (cnt > max_val) {
                max_val = cnt;
            }

        }
        System.out.println(max_val);
    }

    public static class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


}

이번엔 안전영역이란 bfs 를 풀어보았다. 이제 기계적으로 풀어재껴져야 하는데 아직도 고민을 하곤한다. 이제 다음 진도를 나가야 하는데...

이번에도 한번에 맞추지 못하고 틀렸다. 다행히 오류를 찾는 능력이 생겼나 바로 반례를 찾을 수 있었다.

처음에 최대 안전 영역의 개수를 0으로 시작하였는데, 비가 오지 않은 경우 bfs 를 안돌아 그 값이 바뀌지 않았다. 그래서 시작 을 1부터로 하였고 통과하였다.