(JAVA) 백준 2468번 : 안전 영역

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

DFS 관련 문제이다.

 

기존 DFS 문제와는 다른 점이 있다면

 

 

0부터 어느 특정 size까지 하나씩 count를 따진다는 것과

 

각 size 이하는 방문할 수 없다는 것

 

이다.

 

 

 

이를 해결하기 위해

 

map 2차원 배열 내에서 특정 size 초과인 값 과 방문한 적이 없다 는 경우에만

DFS 함수를 호출했고, 상하좌우로 방문 가능한 원소는 방문 체크(boolean true)를 진행했다.

 

*** 높이가 아예 없는 것도 존재하므로, 0부터 특정 size까지 따져봐야 한다.

 

 

감사합니다.

 

 

소스 코드

---

*** DFS 함수 내 y, x 인덱스의 범위에 일치하는 y, x값인 경우에만 재귀 함수 호출을 실행하면

메모리, 시간 측면에서 훨씬 효율적이다. (나는 수정을 안해서 이렇게 글로 적었다.)

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

// 안전 영역
// DFS 사용
public class p2468 {
	static int[][] map;
	static boolean[][] checked;
	static int n;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.valueOf(st.nextToken());
		map = new int[n][n];
		
		int max = 0;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				int height = Integer.valueOf(st.nextToken());
				map[i][j] = height;
				max = Math.max(max, height);
			}
		}
		
		int maxCount = 0;
		
		for(int i = 1; i <= max; i++) {
			int iCount = 0;
			checked = new boolean[n][n];
			
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < n; k++) {
					if(!checked[j][k] && map[j][k] > i) {
						dfs(j, k, i, checked);
						iCount++;
					}
				}
			}
			maxCount = Math.max(iCount, maxCount);
		}
		
		System.out.println(maxCount);
	}
	
	public static void dfs(int y, int x, int height, boolean[][] checked) {
		if((y < 0 || y >= n) || (x < 0 || x >= n)) {
			return;
		}
		
		if(map[y][x] <= height || checked[y][x]) {
			return;
		}
		
		checked[y][x] = true;
		
		dfs(y - 1, x, height, checked);
		dfs(y + 1, x, height, checked);
		dfs(y, x + 1, height, checked);
		dfs(y, x - 1, height, checked);
	}
}

 

 

 

이상입니다.

 

감사합니다!