BOJ_2468_안전영역

1

구분: BFS, DFS

언어: Java

전략:

• 기본 DFS를 푸는 방식을 적용한다.
• 다만 비가 0부터 100까지 오니까 그때마다 조건에 맞는 배열을 새로 생성해주었다. 

 

 

---

2. 코드

import java.util.Arrays;
import java.util.Scanner;
public class BOJ_2468 {

	static int[][] map;
	static int[][] rain;
	static int[] level;
	static int n;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		map = new int[n][n];
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		
		//각 강수량마다 섬의 개수  
		level = new int[101];
		
	
		//비가 오는 cm만큼 반복 0 ~ 100cm 
		for(int c = 0; c<=100; c++) {
			
			int cnt = 0;
			
			//메 반복때마다 map(원본)과 동일한 배열을 생성
			rain = new int[n][n];
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					rain[i][j] = map[i][j];
				}
			}

			
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					//물에 잠기면 0, 안 잠기면 1
					if(rain[i][j]<=c) rain[i][j] = 0;
					else rain[i][j] = 1;	
				}
			}
			
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					if(rain[i][j]==1) {
						cnt++;
						dfs(i, j);
					}
				}
			}
			level[c] = cnt;
			
		}//end for
		
		Arrays.sort(level);
		System.out.println(level[100]);
		
		
	}//main
	
	//탐색하는 dfs함수 
	public static void dfs(int y, int x) {
		
		rain[y][x] = 0;
		
		for(int d = 0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
			if(rain[ny][nx]==0) continue;
			
			dfs(ny, nx);	
		}
	}
	
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};

}

---

3. 

• 삼성 SW 검정 시험 A형 기출 문제라고 한다. 근데 A형 중 역대급 쉬운 난이도 문제라 한다.
• 기본 BFS, DFS를 연습하기 좋은 문제이다. 
• rain이라는 array를 계속 map과 하나하나 복사하는데, 원래는 clone()이라는 함수를 이용했다. 근데 clone()후 굳어져(?)원하는 결과를 낼 수 없었다 --> clone()에 대한 개념 살피기
• 배열을 매 반복문마다 실행하니, 메모리 낭비가 클 것 같다.