[백준/2468] 안전 영역 (Java)
Question
- 문제 링크 : https://www.acmicpc.net/problem/2468
- 분류 : 브루트포스, DFS, BFS
- 풀이 시간 : 50분
문제 해설
- 안전지역 = 일정한 높이의 비가 왔을 때 잠기지 않는 구역
- 주어지는 지역에 많은 비가 내렸을 때, 물에 잠기지 않는 안전 영역이 최대로 몇 개가 만들어지는지 구하여라
Solution
풀이 접근 방법
- "아무 지역도 물에 잠기지 않을 수도 있다." = 비가 안올 때 = height 가 0일 때에도 탐색해야함
- 안전지역 구하기 = DFS + BFS
- 비가 오는 양에 따라 안전지역의 개수가 달라짐 = 브루트포스
정답 코드
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;
}
}
Author And Source
이 문제에 관하여([백준/2468] 안전 영역 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyunjkluz/백준2468-안전-영역-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)