백준 2468번 안전 영역

www.acmicpc.net/problem/2468

2468번: 안전 영역

또 문제가 무슨 말인지 이해하는데 꽤나 걸렸습니다;;

별 대단히 어려운 말도 아닌데 이해가 오래 걸렸네요.

 

내리는 비의 양이 0에서 100까지 점차 높아지고

각 비의 양마다 잠기는 영역이 변합니다.

그에 따라 결정되는 잠기지 않은 구역이 부분 부분 생겨나는데요.

구역들의 수가 가장 많은 비의 양이 있을거고

그 상태에서의 구역들의 수가 답이 되겠습니다.

 

구현한 부분은 다음과 같습니다.

• 비의 높이가 변함에 따라 비에 잠긴 부분 최신화(다 젖었을 시 함수 마침)
• 비의 높이 마다 BFS를 통한 구분된 안전 영역 부분 탐색 및 개수 구하기

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SafetyDomain2468 {
	int[][] map;
	boolean[][] isNotWet;
	boolean[][] isNotVisited;
	Queue<Point> checkQueue = new LinkedList<>();
	
	int[] dirX = {0,0,-1,1};
	int[] dirY = {-1,1,0,0};
	
	int n, domainNum, maxDomain;
	int rain = -1;
	
	public void startRain() {
		int i,j, rainCount = 0;
		maxDomain = 0;
		
		for(i=0; i<n; i++)
			Arrays.fill(isNotWet[i], true);
		while(true) {
			//System.out.println(rainCount);
			//System.out.println(rain);
			rain++;
			domainNum = 0;
			for(i=0; i<n; i++)
				Arrays.fill(isNotVisited[i], true);
			//비 높이 상승 영역 반영
			for(i=0; i<n; i++) {
				for(j=0; j<n; j++) {
					if(isNotWet[i][j] && map[i][j] <= rain) {
						isNotWet[i][j] = false;
						rainCount++;
					}
				}
			}
		
			//만약 영역이 없으면 멈춤
			if(rainCount == n * n)
				break;
			
			for(i=0; i<n; i++) {
				for(j=0; j<n; j++) {
					if(isNotWet[i][j] && isNotVisited[i][j]) {
						bfsRain(i, j);
						domainNum++;
					}
				}
			}
			
			if(domainNum > maxDomain)
				maxDomain = domainNum;
		}
		
		System.out.println(maxDomain);
		
	}
	
	public void bfsRain(int y, int x) {
		int i, nowX, nowY;
		Point nowPoint;
		isNotVisited[y][x] = false;
		checkQueue.add(new Point(x, y));
		
		while(!checkQueue.isEmpty()) {
			nowPoint = checkQueue.remove();
			for(i=0; i<4; i++) {
				nowX = nowPoint.x + dirX[i];
				nowY = nowPoint.y + dirY[i];
				
				if(nowX>=0 && nowX<n && nowY>=0 && nowY<n && map[nowY][nowX] > rain && isNotVisited[nowY][nowX]){
					isNotVisited[nowY][nowX] = false;
					checkQueue.add(new Point(nowX,nowY));
				}
			}
		}
	}
	
	public void setNum() throws IOException {
		int i,j;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf. readLine());
		
		n = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		isNotVisited = new boolean[n][n];
		isNotWet  = new boolean[n][n];

		//Arrays.fill(isNotVisited[i], true);
		for(i = 0; i< n; i++) {
			st = new StringTokenizer(bf. readLine());
			for(j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}	
	}
	/*public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		SafetyDomain2468 main = new SafetyDomain2468();
		main.setNum();
		main.startRain();
	}*/

}

 

 

반성할 점

• 기본적인 부분을 짜는데도 시간이 오래걸려 알고리즘이 어려워진다면 너무 오래 걸릴듯..
• 다른 사람들의 코드를 보니 정말 짧다. (배열, 객체 등 스태틱 그리고 함수도 스태틱으로 하여 짜는듯)
• 앞으로는 더 짧게 짜기!