백준 2468

문제

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

2468번: 안전 영역

import java.util.Scanner;

public class Main2468 {
	
	static int N;
	static int[][] map;
	static boolean[][] visited;
	static int[] ax = {1,-1,0,0};
	static int[] ay = {0,0,1,-1};
	static int max;
	
	public static void dfs(int[][] temp, int x , int y) {
		visited[x][y] = true;
		
		for (int i=0; i<4; i++) {
			int nx = x+ax[i];
			int ny = y+ay[i];
			
			if (nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny]) {
				if (temp[nx][ny] != 0) {
					dfs(temp, nx, ny);
				}
			}
		}
		
	}
	
	public static void heightCheck(int height) {
		int count = 0;
		int temp[][] = new int[N][N];
		
		for (int i=0; i<N; i++) {
			temp[i] = map[i].clone();
		}
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (temp[i][j] <= height) {
					temp[i][j] = 0;
				}
			}
		}
		
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (temp[i][j] != 0 && !visited[i][j]) {	
					dfs(temp,i,j);
					count++;
				}
			}
		}
		
		if (max < count) {
			max = count;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		sc.close();
		
        // 아무지역도 안잠기는 경우의 수도 있기 때문에 0부터 시작
		for (int i=0; i<=100; i++) {
			heightCheck(i);
			visited = new boolean[N][N];
		}
		
		System.out.println(max);
	}
}

1. 오랜만에 어렵지 않게 풀은 문제다. 하지만 첫번째 제출은 오답이었는데 주석처리 부분인 반복문에서 초기식을 i=1로 했기 때문이다. 문제를 다시 보니 아무지역도 안잠길수 있다라는 설정이 맨아래 노트에 적혀있었다.

 

2. 혹시나 해서 0으로 바꿔주니 정답처리 됐다. 문제 해결법은

첫째, 임시2차원 배열 생성 후 매 반복마다 초기화 및 map배열 깊은 복사

둘째, 강수량(main메소드 안에 마지막 반복문의 i)이하인 지역의 높이를 0으로 변환

셋째, temp배열을 깊이우선탐색하며 0을 만나기 전까지 방문체크

넷째, 지역의 높이가 1~100이기에 각 높이마다 방문배열을 초기화

 

3. 다만 백준 문제의 경우 하단에 문제 분류가 나와있기에 dfs방식으로 접근을 했는데 만약 실제 코테라면 dfs로 풀지 bfs로 풀어야 할지 헷갈릴듯하다. 두 방식을 언제써야하는지에 대해서도 추가적으로 알아보자.