[백준/2468] 안전 영역 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/2468
• 분류 : 브루트포스, DFS, BFS
• 풀이 시간 : 50분

문제 해설

1. 안전지역 = 일정한 높이의 비가 왔을 때 잠기지 않는 구역
2. 주어지는 지역에 많은 비가 내렸을 때, 물에 잠기지 않는 안전 영역이 최대로 몇 개가 만들어지는지 구하여라

Solution

풀이 접근 방법

1. "아무 지역도 물에 잠기지 않을 수도 있다." = 비가 안올 때 = height 가 0일 때에도 탐색해야함
2. 안전지역 구하기 = DFS + BFS
3. 비가 오는 양에 따라 안전지역의 개수가 달라짐 = 브루트포스

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static class Node {
    int x, y;

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

  static int N;

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    N = Integer.valueOf(br.readLine());
    int[][] map = new int[N][N];
    // 건물의 높이 종류를 담는 집합 -> 잠길 건물이 있을 때에만 탐색을 돌리기 위함
    HashSet<Integer> heightSet = new HashSet<Integer>();
    StringTokenizer st;

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

      for (int j = 0; j < N; j++) {
        map[i][j] = Integer.valueOf(st.nextToken());
        heightSet.add(map[i][j]);
      }
    }

    // 비가 안올 때의 경우를 추가
    heightSet.add(0);

    ArrayList<Integer> answer = new ArrayList<Integer>();
    boolean[][] visited;

    // height 만큼의 비가 왔을 때의 안전구역을 구함
    for (Integer height : heightSet) {

      visited = new boolean[N][N];
      int safeZone = 0;

      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          // 온 비의 높이보다 높은 지역만 탐색
          if (map[i][j] > height && !visited[i][j]) {
            safeZone += 1;
            BFS(i, j, height, visited, map);
          }
        }
      }

      // 구해진 안전구역의 개수를 담음
      answer.add(safeZone);
    }

    // 안전구역의 개수를 내림차순 정렬
    Collections.sort(answer, Collections.reverseOrder());
    bw.write(answer.get(0) + "\n");
    bw.flush();
    bw.close();

  }

  static void BFS(int x, int y, int height, boolean[][] visited, int[][] map) {
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };
    Queue<Node> queue = new LinkedList<Node>();

    queue.add(new Node(x, y));
    visited[x][y] = true;

    while (!queue.isEmpty()) {
      Node n = queue.poll();

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

        // 범위 밖이거나, 이미 탐색했거나, 내린 비보다 낮은 구역이면 통과
        if (!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] <= height)
          continue;

        visited[nx][ny] = true;
        queue.add(new Node(nx, ny));
      }
    }
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < N)
      return true;
    return false;
  }

}