import java.util.*;
/*
[백준] 2468번 - 안전영역 (Java)
*/
public class Main {
static int N;
static int A[][];
static boolean visited[][];
static int max_height = 0;
void InputData() {
Scanner in = new Scanner(System.in);
N = in.nextInt();
A = new int[N][N];
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
A[i][j] = in.nextInt();
max_height = Math.max(A[i][j], max_height);
}
}
}
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void DFS(int x, int y) {
visited[x][y] = true;
for (int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (A[nx][ny] <= rain) continue;
if (visited[nx][ny]) continue;
DFS(nx, ny);
}
}
int count;
int rain = 0;
void Solve() {
int max = Integer.MIN_VALUE;
while (rain <= max_height) {
visited = new boolean[N][N];
count = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (A[i][j] <= rain) continue;
if (visited[i][j]) continue;
DFS(i, j);
count++;
}
}
rain++;
max = Math.max(max, count);
}
System.out.println(max);
}
public static void main(String[] args) {
Main m = new Main();
m.InputData();
m.Solve();
}
}
* 2차 풀이
<문제분석> 맵 정보로 숫자(높이)가 주어진다. 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 몇개인지 계산하는 문제이다. 안전영역은 물에 잠기지 않는 영역이 상하좌우로 연결된 지역을 뜻한다.
<입력범위> 맵의 행과 열을 뜻하는 N은 2 ~ 100이하의 정수이다. 높이는 1 ~ 100이하의 정수이다.
<풀이 - BFS> 1. 비의 양에 따라 안전영역의 갯수는 달라진다. - for (i = 2 to max_h) - max_h는 입력함수에서 미리 알아놓자. - 루프를 돌다가 map[x][y] > i 이면 방문처리를 하고 BFS탐색을 시작하자. - group_num++를 해서 BFS를 호출 할 때마다 파라미터로 같이 넘겨주자. - group_num를 높이가 달라질 때마다 최대값으로 저장하자. - 높이가 달라지면 방문배열 초기화 2. BFS탐색 - 맵에서 하나의 안전영역을 확보하는 것이 목적 3. 아무지역도 물에 잠기지 않는 경우 예외처리 4. group_num의 최대값을 구하면 된다.
- 알고리즘 구상 : 16분
- 최대 시간복잡도 계산 100(빗물높이) * 100(행) * 100(열) = 1,000,000번 BFS 호출됨.
- 코드 구현 : 28분
- 디버깅 & 예외처리 : 10분 이유 : 높이가 2 ~ 100 정수여서 물높이를 2부터 시작했다. 하지만 아무 지역도 물에 잠기지 않을 수 있다는 말은 물 높이가 2이하일 수 있다는 말이로 0부터 시작해야 한다.
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.lang.Math;
//[백준] 2468번 - 안전영역 (Java)
public class Main {
static int N;
static int map[][];
static boolean visited[][];
static int max_count = Integer.MIN_VALUE;
static int safe_num = 0;
static int max_h = Integer.MIN_VALUE;
static boolean H[];
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public void InputData() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
map = new int[N][N];
H = new boolean[100+1];
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
map[i][j] = sc.nextInt();
max_h = Math.max(max_h, map[i][j]); // 최대 높이 저장
H[map[i][j]] = true; // 입력된 높이일 경우에만 true
}
}
}
static int dx[] = {-1, 0, 1, 0};
static int dy[] = {0, 1, 0, -1};
public void BFS(int x, int y, int h) {
Queue<Point> Q = new LinkedList<>();
visited[x][y] = true; // 탐색 시작점 방문처리
Q.add(new Point(x, y)); // 큐에 삽입
while (!Q.isEmpty()) {
Point now = Q.poll(); // 큐에서 하나 가져옴
for (int i=0; i<4; i++) { // 현위치에서 상하좌우 탐색 시작
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 맵을 벗어나면 패스
if (map[nx][ny] <= h) continue; // 산높이가 물높이보다 낮으면 잠기므로 패스
if (visited[nx][ny]) continue; // 이미 방문한 지역이면 패스
visited[nx][ny] = true;
Q.add(new Point(nx, ny));
}
}
}
public void Solve() {
H[0] = H[1] = true;
for (int t=0; t<max_h; t++) { // 빗물높이마다 맵 전체 탐색해서 안전지역 카운트
if (H[t] == false) continue; // 빗물높이가 입력된 높이가 아니면 패스
safe_num = 0;
visited = new boolean[N][N]; // 방문배열 초기화
for (int i=0; i<N; i++) { // 맵 탐색
for (int j=0; j<N; j++) {
if (map[i][j] <= t) continue; // 산높이가 빗물높이(t) 이하면 패스
if (visited[i][j]) continue; // 방문한 곳이면 패스
BFS(i, j, t); // 안전지역 bfs 탐색 시작
safe_num++; // 안전지역 번호 증가
}
}
max_count = Math.max(max_count, safe_num); // 언전지역 갯수 최대값 저장
}
System.out.println(max_count);
}
public static void main(String[] args)
{
Main m = new Main();
m.InputData();
m.Solve();
}
}
<코드구현 #3>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
/*
1. FloodFill 알고리즘을 돌리는데 입력받은 높이갯수만큼 돌린다.
- 특정 높이 이하는 다 물에 잠기니까 높이와 높이 사이의 수는 탐색할 필요가 없다.
- 높이가 달라질 때마다 FloodFill 알고리즘을 새로 돌려야 한다. (방문재열 초기화)
- FloodFill 한번 돌릴 때마다 안전영역의 갯수를 최대값 갱신한다.
2. 가지치기(FloodFill)
- 입력된 높이 이하만 체크
- 높이 이하
- 방문한 곳
3. 가지치기(BFS)
- 맴 범위
- 높이 이하
- 방문한 곳
※ 아무지역도 물에 잠기지 않을 수 있다.
- 물 높이가 0일때 안전지역은 1이므로 max_count의 최소값은 1이 된다.
- max_count를 Integer.MIN_VALUE나 0으로 초기화를 하면 80%에서 통과가 안된다.
*/
public class Main {
static int N;
static boolean visited[][];
static boolean H[];
static int map[][];
static int dx[] = {-1, 0, 1, 0};
static int dy[] = {0, 1, 0, -1};
class Node {
int x, y;
public Node (int x, int y) {
this.x = x;
this.y = y;
}
}
void BFS(int x, int y, int h) {
Queue<Node> Q = new LinkedList<>();
Q.add(new Node(x, y));
visited[x][y] = true;
while(!Q.isEmpty()) {
Node now = Q.poll();
for (int i=0; i<4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
// 가지치기
if (nx<0 || nx>=N || ny<0 || ny>=N) continue; // 범위 벗어나면 패스
if (map[nx][ny] <= h) continue; // 물에 잠겼으면 패스
if (visited[nx][ny]) continue; // 방문했으면 패스
// 탐색성공
visited[nx][ny] = true; // 방문체크
Q.add(new Node(nx, ny)); // 큐에 삽입
}
}
}
void Solve() {
int count = 0;
int max_count = 1;
// 높이 최소값 ~ 최대값
for (int h=1; h<=100; h++) {
// 가지치기
if (H[h] == false) continue; // 입력된 높이가 아니면 패스
// 높이가 h일때 그 이하인 지역은 모두 물에 잠긴다.
visited = new boolean[N][N];
count = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (map[i][j] <= h) continue;
if (visited[i][j]) continue;
BFS(i, j, h);
count++;
}
}
max_count = Math.max(max_count, count);
}
System.out.println(max_count);
}
void inputData() throws Exception {
InputStreamReader reader = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(reader);
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
H = new boolean[101]; //높이는 1 ~ 100
for (int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
H[map[i][j]] = true;
}
}
}
public static void main(String[] args) throws Exception {
Main m = new Main();
m.inputData(); // 입력 받는 부분
m.Solve();// 여기서부터 작성
}
}
댓글