[백준] 2468.안전 영역 / DFS

@DFS / 22m (필기 5m)

조건이 헷갈려서 4-5번 틀렸다.

edge case에 대해 조금 더 깊게 생각해보는 습관 필요

 

 

문제 링크

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

2468번: 안전 영역

 

 

삽질 포인트

1.

높이가 1~100 이므로

비가 오는 높이의 for문을 1-100까지 돌려야 하는데 이때 머리를 쓴다고

 

비가 1만큼 오면 어차피 다 잠기니까 안전영역이 0개가 되고,

비가 100만큼 오면 하나도 안 잠기니까 안전영역이 1개가 된다고 생각해서

2-99까지만 돌렸다가 틀렸다.

일단 이렇게 스스로 생각하고 결론지어서 케이스를 임의로 지워버리고 안 돌리는건 굉장히 위험하다.

 

그리고 문제에 보면

아무 지역도 물에 잠기지 않을 수도 있다.

라는 말이 있는데

 

이 말 뜻이 비가 안 올 수도 있다는 것인지, 아니면 높이가 100보다 높은게 있다는 건지는 모르겠지만

이 조건 때문에 비가 안 오는 경우를 추가해서 0부터 100까지 돌리게끔 수정했다.

 

2.

그리고 처음에는 max를 1로 해뒀는데, 이렇게 해 두면 비가 와서 다 잠겨버리는 경우에도 값이 1이 나와서 이론상으로 맞지 않다

(이때도 코드는 맞았다고 떴는데.. 이유는 "아무 지역도 물에 잠기지 않을 수도 있다." 이것 때문인 것 같다)

 

맞는 방법은 -1 또는 Integer.MIN_VALUE 로 놓고 푸는 것이다. (+종만북)

그러다 틀리면 어떡하지 하고 무서울 수 있지만

적어도 여러 경우 중 한번은, 안전영역이 0이나 1, 또는 그 이상이 나올 것이기 때문에 저렇게 두고 풀어도 된다.

 

이렇게 두고 푸는 것의 장점은 최솟값이 0일지 1일지를 내가 생각할 필요가 없다.

만약 내가 1로 최솟값을 두고 푼다면 틀렸을 때 아 저게 틀린건가? 0으로 고쳐야 하나 고민하고 생각해야 하지만

애초에 나올 수 없는 값을 지정해 두면 그 영역은 이제 내가 생각할 필요가 없는, 컴퓨터의 영역이다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

	//적어도 -1은 안나올테니까, 한번은 다른 값이 나올테니까 max는 -1로 두고 해야 함 
	static int N, map[][], max = -1;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static boolean[][] check;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = stoi(br.readLine());
		map = new int[N][N];
		check = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				map[i][j] = stoi(st.nextToken());
		}
		
		//비가 하나도 안올 수도 있으니까 0부터 
		for (int i = 0; i <= 100; i++) {
			for (int j = 0; j < N; j++)
				Arrays.fill(check[j], false);
			
			int safeZone = findStart(i);
			if (max < safeZone) max = safeZone;
		}
		System.out.println(max);
	}

	private static int findStart(int h) {
		int count = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j] && map[i][j] > h) {
					check[i][j] = true;
					dfs(i, j, h);
					count++;
				}
			} 
		}
		return count;
	}

	private static void dfs(int x, int y, int h) {
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			
			if (!check[nx][ny] && map[nx][ny] > h) {
				check[nx][ny] = true;
				dfs(nx, ny, h);
			}
		}
	}

	private static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

ㅎㅎ1년전보다 두배 빨라짐!

끗!