[백준] 2468번 안전 영역 (C++, JAVA)

2468번: 안전 영역

안전한 영역의 개수 중 최댓값을 출력하는 문제이다.

먼저 입력받을 때 높이 중 최대 높이를 구한 후

높이 1부터 최대 높이까지 비교해야 한다.

 

원래 이런 BFS문제들을 풀 때 입력 배열의 비교가 끝나면 값을 0으로 만들어주었지만

이번엔 한 입력 배열로 여러 번 비교해 줘야 하기 때문에

따로 visited 배열을 만들어서 방문 여부를 체크해준다.

 

BFS의 원리는

현재 위치(큐의 front)를 기준으로 상하좌우를 비교해 주는데

안전한 영역일 때인

현재 위치의 높이(area[i][j]) > 비교 대상인 높이(k)

인 경우에만 visited에 체크해 주고 큐에 넣어준다.

이때 visited가 체크되어 있는지도 구분해준다.

 

이렇게 큐가 empty될 때까지

큐의 front의 상하좌우를 반복해 주고

BFS함수를 나오면 카운트 해준다.

 

이런 식으로 k의 값이 바뀔 때마다 카운트의 값과 최댓값(default=1)을 비교해 준 뒤

최댓값을 출력해주면 끝

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int cnt = 0, Max = 1, x, y;
void Bfs(int k, int i, int j, int N, int area[][101], int visited[][101]) {
	queue <pair<int, int>> q;
	q.push(pair<int, int>(i, j));
	visited[i][j] = 1;
	while (!q.empty()) {
		x = q.front().first, y = q.front().second;
		if (x - 1 >= 0 && area[x - 1][y] > k && !visited[x - 1][y]) { //상
			q.push(pair<int, int>(x - 1, y));
			visited[x - 1][y] = 1;
		}
		if (x + 1 < N && area[x + 1][y] > k && !visited[x + 1][y]) { //하
			q.push(pair<int, int>(x + 1, y));
			visited[x + 1][y] = 1;
		}
		if (y - 1 >= 0 && area[x][y - 1] > k && !visited[x][y - 1]) { //좌
			q.push(pair<int, int>(x, y - 1));
			visited[x][y - 1] = 1;
		}
		if (y + 1 < N && area[x][y + 1] > k && !visited[x][y + 1]) { //우
			q.push(pair<int, int>(x, y + 1));
			visited[x][y + 1] = 1;
		}
		q.pop();
	}
}

int main() {
	int N;
	cin >> N;
	int area[101][101] = { 0 }, highest = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> area[i][j];
			highest = max(highest, area[i][j]);
		}
	}

	for (int k = 1; k <= highest; k++) {
		int visited[101][101] = { 0 };
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (area[i][j] > k && !visited[i][j]) {
					Bfs(k, i, j, N, area, visited);
					cnt++;
				}
			}
		}
		Max = max(Max, cnt);
		cnt = 0;
	}

	cout << Max;

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_2468_안전영역 {
	private static int N, tmp, res = 1;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static boolean visited[][];
	
	public static void dfs(int X, int Y, int depth) {
		visited[X][Y] = true;
		for(int i = 0; i < 4; i++) {
			int x = X + dx[i], y = Y + dy[i];
			if(x < 0 || x >= N || y < 0 || y >= N || arr[x][y] <= depth || visited[x][y]) continue;
			visited[x][y] = true;
			dfs(x, y, depth);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); arr = new int[N][N];
		int rain = 1;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
				rain = Math.max(rain, arr[i][j]);
			}
		}
		for(int k = 1; k <= rain; k++) {
			tmp = 0; visited = new boolean[N][N];
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(arr[i][j] <= k || visited[i][j]) continue;
					tmp++;
					dfs(i, j, k);
				}
			}
			res = Math.max(res, tmp);
		}
		System.out.println(res);
	}
}