백준 2468 안전 영역

백준 2468 안전 영역

1. 문제 링크

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

2468번: 안전 영역

 

2. 문제 해결에 대한 아이디어

1. 내린 비의 양에 따라 각 케이스 별로 안전 영역의 개수를 세야 한다.

2. 코딩할 때는, input 값 중 최대 높은 숫자부터 하나씩 줄여갔지만 현재 시점에선 그럴 필요 없다고 판단한다.

   . 내린 비의 높이를 0부터 차례대로 증가시키며 안전 영역의 개수를 세고 개수가 0일 때 끝내면 되었을 것 같다.

3. 내린 비의 높이 별로 조사하여 발생하는 안전영역의 개수를 구한다.

4. 안전영역의 높이는 내린 비의 높이보다 큰 경우에 해당한다.

5. 각 케이스를 조사할 때마다, visit 배열을 초기화해야 한다.(이 전 케이스에서 안전영역이라고 마킹했기 때문)

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N;
	static int[][] board;
	static boolean[][] visit;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static Queue<Loc> q = new LinkedList<>();
	static int maxSafe = 0;
	static int maxH = 0;
	static int nowH = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().split(" ")[0]);
		board = new int[N][N];
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				maxH = Math.max(maxH, board[i][j]);
			}
		}

		while (maxH >= 0) { // 가장 많이 오는 장마부터 안 올때까지
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j] > maxH && !visit[i][j]) {
						q.add(new Loc(i, j));
						BFS();
						cnt++;
					}
				}
			}

			maxSafe = Math.max(maxSafe, cnt);
			visit = new boolean[N][N];
			q.clear();
			maxH--;
		}

		System.out.println(maxSafe);
		br.close();

	}

	static void BFS() {

		while (!q.isEmpty()) {
			Loc now = q.poll();
			int y = now.y;
			int x = now.x;
			visit[y][x] = true;
			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];
				if (yy < 0 || xx < 0 || yy >= N || xx >= N || 
						visit[yy][xx] || board[yy][xx] <= maxH)
					continue;

				q.add(new Loc(yy, xx));
				visit[yy][xx] = true;

			}
		}

	}
}

class Loc {
	int y, x;

	public Loc(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 위에도 작성했지만, 모두 잠기는데 필요한 비의 높이를 구한다고 괜히 input 값 중 가장 높은 높이를 구했다.

2. 이 로직을 수정하면 수행 시간이 좀 더 빨리 나올 것이라고 생각한다.