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

#2468 안전 영역

난이도 : 실버 1 

유형 : 그래프 탐색 / DFS

2468번: 안전 영역

▸ 문제

▸ 입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

▸ 출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

 

 

문제 풀이  

물의 높이를 1부터 시작해서 물에 잠기지 않는 안전영역의 최대 갯수를 구하는 문제이다.

 

📚 조건

• 2 <= N <= 100
• 1 <= 높이 <= 100

 

브루트포스와 DFS 탐색을 사용하여 조건만 잘 적용해줘서 구현하면 된다.

→ BFS 대신 DFS탐색을 선택한 이유는 해당 영역의 모든 노드를 끝까지 빠르게 탐색하는데 더 용이하기 때문이다. 

맨 밑에 BFS, DFS 성능 비교 확인

 

구상

1. 각 높이에 따라 브루트포스로 맵을 전체탐색을 한다.
2. 탐색 도중 안전지역이 있으면 해당 지역을 시작으로 DFS탐색을 시작한다. map[i][j] > height
3. 안전지역 DFS 탐색이 끝났으면 cnt를 센다.
4. height에 따라 나온 cnt 중 최댓값을 출력한다.

 

풀이 코드  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[][] map;
	static boolean[][] checked;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0,- 1, 0, 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];
		
		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());
				if(map[i][j] > maxHeight) {
					maxHeight =map[i][j];
				}
			}
		}
		
		int max =0;
		// 1. 모든 지역 탐색
		for(int height=0; height<maxHeight+1; height++) {
			checked = new boolean[n][n];
			int cnt=0;
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					// 2. 안전 영역 탐지
					if(!checked[i][j] && map[i][j] > height){
						cnt+=dfs(i,j,height); // 해당 안전영역 탐색 시작
					}
					
				}
			}
			max = Math.max(max, cnt);
		}
		System.out.println(max);
	}
	// 안전 영역 DFS탐색
	static int dfs(int x, int y, int height) {
		checked[x][y] = true;
		for(int i=0; i<4; i++) {
			int nx = x +dx[i];
			int ny = y +dy[i];
			
			if(nx<0 || ny<0 || nx>n-1 || ny >n-1) continue;
			if(checked[nx][ny]) continue;
			if(map[nx][ny]> height) {
				dfs(nx,ny, height);
			}
		}
		return 1;
	}
}

 

 

BFS로 구현하면 다음과 같다

static int bfs(int x, int y, int height) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{x,y});
		check[x][y] = true;
		
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			int px = pos[0];
			int py = pos[1];
			
			for(int i=0; i<4; i++) {
				int nx = px +dx[i];
				int ny = py +dy[i];
				
				if(nx<0 || ny<0 || nx>n-1 || ny >n-1) continue;
				if(check[nx][ny]) continue;
				if(map[nx][ny]> height) {
					check[nx][ny] = true;
					q.add(new int[] {nx,ny});
				}
			}
		}
		return 1;
	}

 

 

해당 문제에 BFS와 DFS의 성능을 비교해보았다.

BFS탐색 결과

 

DFS탐색 결과

 

조금이나마 DFS의 탐색속도가 더 빠른 것을 확인할 수 있다.