백준 2468 안전 영역 JAVA

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

• bfs를 이용한다.

• 시간복잡도 O(N)은 최대 높이(100) X map을 도는 이중for문(100X100) X 이중for문 사용횟수이므로 O(N) = 1,000,000이다. 그래서 삼중for문을 사용했다.

• 0부터 maxHeight까지 반복문을 돌며 빗물을 채운다(visited[][] = true로 설정(fillTheMap))
  -> 전체 map을 돌며 false인 좌표값을 기준으로 bfs를 수행한다. (solution)
  -> 안전영역(cnt) 값을 구한 후 answer와 비교하여 최대값을 answer에 저장한다.
  -> visited[][] 배열을 다시 false로 초기화한다.(initVisited)
  -> 다시 위에서부터 반복

• 틀린 이유 : 물의 높이가 0일 경우 안전지역의 개수가 1일 수 있다. 따라서 초기 answer의 값을 0이 아닌 1로 둔다.

---

코드

정답 코드

/**
 * 2468_안전 영역
 *
 * 시간 복잡도 : 최대 높이(100) * map을 도는 이중for문(100*100) * 3
 *             O(N)은 100만이므로 1억 미만이기 때문에 for문 3개를 썼다.
 *
 * 0부터 maxHeight까지 반복문을 돌며 빗물을 채운다(visited[][] = true로 설정)
 * -> 전체 map을 돌며 false인 좌표값을 기준으로 bfs를 수행한다.
 * -> 안전영역(cnt) 값을 구한 후 answer와 비교하여 최대값을 answer에 저장한다.
 * -> visited[][] 배열을 다시 false로 초기화한다.
 * -> 다시 위에서부터 반복
 *
 * 틀린이유 : 물의 높이가 0일 경우 안전지역의 개수가 1일 수 있다.
 *      -> 초기 answer의 값을 0이 아닌 1로 놓는다.
 */

public class P_2468 {
    static int N;
    static int[][] map; // 주어진 숫자 지도
    static boolean[][] visited; // 방문처리를 위한 지도
    static int answer = 1; // 안전 영역의 최대 개수(답)
    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        // 주어진 값 중 최대 값
        int maxHeight = 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());
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }

        // 0부터 주어진 최대 값까지 반복문을 수행한다.
        for (int i = 0; i <= maxHeight; i++) {
            int cnt = 0;

            fillTheMap(i);
            cnt = solution(cnt);

            answer = Math.max(answer, cnt);

            initVisited();
        }

        System.out.println(answer);
    }

    // visited배열을 전부 false로 다시 수행
    private static void initVisited() {
        for (int i = 0; i < visited.length; i++) {
            Arrays.fill(visited[i], false);
        }
    }

    // map 전체를 돌며 해당 좌표가 false(빗물이 채워지지 않음)인 경우 bfs를 수행한다.
    private static int solution(int cnt) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (!visited[i][j]) {
                    bfs(new Point(i,j));
                    cnt++;
                }
            }
        }
        return cnt;
    }

    // 0부터 최대 높이까지 빗물을 채운다.
    private static void fillTheMap(int height) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] <= height) {
                    visited[i][j] = true;
                }
            }
        }
    }

    // bfs 동작
    static void bfs(Point point) {
        Queue<Point> pq = new LinkedList<>();
        pq.offer(point);

        while (!pq.isEmpty()) {
            Point p = pq.poll();

            for (int i = 0; i < 4; i++) {
                int y = p.y + my[i];
                int x = p.x + mx[i];

                if (0<=x && x<N && 0<=y && y<N) {
                    if (!visited[y][x]) {
                        visited[y][x] = true;
                        pq.offer(new Point(y,x));
                    }
                }
            }
        }
    }

    static class Point {
        int y;
        int x;

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