[백준] 2468번: 안전 영역(완전탐색, 그래프)

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

2468번: 안전 영역

코드

import java.util.Scanner;

public class Main {
	static int map[][];			// 2차원 배열
	static boolean visit[][];	// 방문한 영역 확인
	static int[] dx = {0, -1, 0, 1};	// 상하좌우
	static int[] dy = {-1, 0, 1, 0};
	static int N;	// 배열 사이즈 입력받는 변수
	static int safeSpaceMax = 1;
	
	// 매개변수: x좌표, y좌표, 높이
	public static void dfs(int x, int y, int h) {
		
		// x, y 좌표가 지도의 범위를 벗어났을경우
		if(x<0 || x>=N || y<0 || y>=N)
			return;
		
		// 이미 방문한 위치 OR 높이 이하(물에 잠긴)인 경우.
		if(visit[x][y] || map[x][y] <=h)	
			return;
		
		visit[x][y] = true;	// 해당 x, y좌표 => 방문 체크
		
		for(int i=0; i<4; i++) {	// 상하좌우 확인
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && ny>=0 && nx<N && ny<N) {	// 해당 지도의 범위 이내여야함.
				if(map[nx][ny] > h && visit[nx][ny] == false)	// 안잠기는곳 && 방문하지 않은 곳
					dfs(nx, ny, h);	// dfs 호출
			}
		}
	}

	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		map = new int[N][N];
		//visit = new boolean[N][N];
		int max = 0;	// 입력받은 2차원 배열의 정수 중 높이 최댓값 저장	
		int result = 1;	// 안전영역이 최대인 갯수(출력할 변수)
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = scan.nextInt();
				if(map[i][j] > max)	// 최대 높이 저장
					max = map[i][j];
			}
		}
		
		// 1부터 최대 높이만큼까지 안전영역이 최대인 갯수 찾기.
		for(int i=1; i<=max; i++) {	
			visit = new boolean[N][N];	// 각 높이마다 방문 영역 초기화
			int count = 0;	// 각 높이마다 안전영역의 갯수 초기화
			for(int j=0; j<N; j++) {
				for(int k=0; k<N; k++) {
					// 잠기지 않는곳 && 방문하지 않은 곳
					if(map[j][k] > i && visit[j][k] == false) {
						count ++;
						dfs(j, k, i);
					}
				}
			}
			// i 높이의 모든 탐색이 끝나면 이전과 비교해 크기가 최대인 영역 구하기.
			result = Math.max(result, count);	
		}
		System.out.println(result);
		scan.close();
	}

}

문제 이해

 - N*N 2차원 배열에서 해당 높이보다 낮거나 같은 지점은 물에 잠긴다.

 - 물에 잠기지 않는 안전한 영역은 물에 잠기지 않는 지점들이 상하좌우에 인접해 있으며, 그 크기가 최대인 영역이다.

 

문제 예시처럼, 만약 높이가 4 이하인 지점이 물에 잠겼다고 가정했을 때,

문제 예시처럼, 만약 높이가 4 이하인 지점이 물에 잠겼다고 가정했을 때,

 

위와 같이 물에 잠기지 않는 안전한 영역은 5개가 된다.

 

 

풀이

Main()

* 먼저 문제에서 주어진 2차원 배열 중 최댓값(최대 높이)를 구한다.

  -> 1부터 최대높이까지 각 높이별 안전한 영역의 갯수를 구해서 최대 영역을 구하면 되므로,,

for(int i=0; i<N; i++) {
	for(int j=0; j<N; j++) {
		map[i][j] = scan.nextInt();
		if(map[i][j] > max)	// 최대 높이 저장
			max = map[i][j];
	}
}

 

 

* 위에서 구한 최대높이를 1부터 최대높이(max)까지 for문을 돌린다.

* 그 후 각 높이별 방문배열(visit)를 초기화 하고, 각 높이별 안전 영역의 갯수(count)를 초기화 한다.

// 1부터 최대 높이만큼까지 안전영역이 최대인 갯수 찾기.
for(int i=1; i<=max; i++) {	
	visit = new boolean[N][N];	// 각 높이마다 방문 영역 초기화
	int count = 0;	// 각 높이마다 안전영역의 갯수 초기화

 

* 그 후 2중 for문을 통해 잠기지 않은곳(2차원 배열의 값이 높이보다 큰곳) && 방문하지 않은곳은

  재귀호출을 통해 잠기지 않았고, 방문하지 않은 모든 곳을 찾는다.

 

for(int j=0; j<N; j++) {
	for(int k=0; k<N; k++) {
		// 잠기지 않는곳 && 방문하지 않은 곳
		if(map[j][k] > i && visit[j][k] == false) {
			dfs(j, k, i);
			count ++;
		}
	}
}
// i 높이의 모든 탐색이 끝나면 이전과 비교해 크기가 최대인 영역 구하기.
result = Math.max(result, count);	

 

dfs()

* 매개변수 x, y좌표가 지도의 범위를 벗어날 경우 => dfs 종료

* 매개변수 x, y좌표가 방문한 위치이거나 물에 잠긴 경우 => dfs 종료

 

* 해당 매개변수 => 방문 체크

* 상, 하, 좌, 우 체크하며 지도의 범위 이내이고, 안잠긴곳 && 방문하지 않은곳 -> 계속해서 탐색(재귀호출)

// 매개변수: x좌표, y좌표, 높이
public static void dfs(int x, int y, int h) {
	
	// x, y 좌표가 지도의 범위를 벗어났을경우
	if(x<0 || x>=N || y<0 || y>=N)
		return;
		
	// 이미 방문한 위치 OR 높이 이하(물에 잠긴)인 경우.
	if(visit[x][y] || map[x][y] <=h)	
		return;
		
	visit[x][y] = true;	// 해당 x, y좌표 => 방문 체크
		
	for(int i=0; i<4; i++) {	// 상하좌우 확인
		int nx = x + dx[i];
		int ny = y + dy[i];
			
		if(nx>=0 && ny>=0 && nx<N && ny<N) {	// 해당 지도의 범위 이내여야함.
			if(map[nx][ny] > h && visit[nx][ny] == false)	// 안잠기는곳 && 방문하지 않은 곳
				dfs(nx, ny, h);	// dfs 호출
		}
	}
}