백준_안전영역_2468[Java]

문제

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

2468번: 안전 영역

 

풀이

발생할 수 있는 그룹의 최대 갯수를 구하는 문제이다.

그루핑 문제를 푼 지 좀 오래되서 처음에 어렵게 느껴졌지만 생각보다 쉬웠다.

그룹의 갯수를 구하되 최대의 갯수를 구하면 되기 때문 ! 

 

main 메소드의 흐름

1. 주어진 영역 내의 최소와 최대 높이 값을 구해서 잠길 수 있는 높이의 경우의 수를 모두 확인해야 한다. 

2. 물에 잠기지 않은 영역을 기준으로 DFS 탐색을 하여 하나의 그룹을 구한다.

    이를 더 이상 존재하는 그룹이 없을때까지 탐색하며 한 그룹을 구할 때마다 그룹의 갯수(cnt)를 +1해준다.

    이 때 그루핑이 제대로 되게 한 번 방문한 위치와 이미 물에 잠긴 영역은 방문하지 않는다. (효율성 높이기)

    * 물의 높이가 달라질 때마다 방문 배열을 초기화해준다.

3. 그룹의 갯수를 result 변수에 담아 최댓값을 저장해둔다. 

 

DFS 메소드의 흐름 

1. 기저사례를 확인한다. 

    - 장외로 다음 위치가 넘어왔을 경우

    - 이미 방문한 위치거나 물에 잠긴 영역일 경우

 

2. 방문한 위치라는 것을 저장해주고 visit[y][x] = true;

3. 현재 위치 기준, 동서남북 위치로 탐색한다. 

 

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N;
	static int[][] section;
	static boolean[][] visit; 

	static int cnt = 0;
	
	// 좌 상 우 하 
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		section = new int[100][100];
		visit = new boolean[100][100];
		int max = 0; 
		int min = 100;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				section[i][j] = sc.nextInt(); // 높이는 100이하 
				if(section[i][j] > max) max = section[i][j];
				if(section[i][j] < min) min = section[i][j];
			}
		}
		sc.close();
		
		int result = 1;
		for(int i = min; i < max; i++) {
			cnt = 0;
			
			for(int j = 0; j < 100; j++) {
				Arrays.fill(visit[j], false);
			}				
			
			for(int y = 0; y < N; y++) {
				for(int x = 0; x < N; x++) {
					if(!visit[y][x] && section[y][x] > i) { // 물에 잠기지 않은 곳만 확인 
						dfs(x,y,i);
						cnt++;
					}
				}
			}
			
			result = Math.max(result, cnt);
		}
		
		System.out.println(result);
		
		
	}

	private static void dfs(int x, int y, int height) {
		
		// 장외 
		if(x < 0 || x >= N || y < 0 || y >= N) {
			return;
		}
		
		// 이미 방문한 위치거나 물에 잠긴 위치거나 
		if(visit[y][x] || section[y][x] <= height) {
			return;
		}
			
		visit[y][x] = true;
		
		for(int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			
			dfs(nextX, nextY, height);
		}
		
	}

}

 

참고

https://debuglog.tistory.com/92

백준 2468번 - 안전 영역