알고리즘(BOJ)/Silver

백준 - 안전 영역 2468

ch.0 2023. 2. 9. 17:14


문제 분석

비가 오는 높이를 1씩 높혀주면서 잠긴곳은 0 으로 바꿔주었다.

그리고 BFS를 태워서 0이아닌곳이 막힐때까지 0으로 확장시켜 주었다.

 

 

 

 

 

전체 소스

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

public class Main {
	static int size, cnt, result;
	static int[][] array;

	public static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visited = new boolean[size][size];

		boolean check = true;
		int[][] array_c = new int[size][size];
		for(int i=0; i<array.length; i++) {
			array_c[i]=array[i].clone();
		}
		
		cnt=0;
		while (check) {
			check = false;
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (array_c[i][j] != 0) {
						array_c[i][j] = 0;
						visited[i][j] = true;
						q.offer(new int[] { i, j });
						check = true;
						cnt++;
						break;
					}
				}
				if (check == true)
					break;

			}
			int[] x_move = { 0, 0, -1, 1 };
			int[] y_move = { -1, 1, 0, 0 };

			while (!q.isEmpty()) {
				int[] p = q.poll();
				int x = p[0];
				int y = p[1];
	
				


				for (int i = 0; i < 4; i++) {
					int x_p = x + x_move[i];
					int y_p = y + y_move[i];
					if (x_p >= 0 && y_p >= 0 && x_p < size && y_p < size) {
						if (array_c[x_p][y_p] != 0 && visited[x_p][y_p] == false) {
							array_c[x_p][y_p] = 0;
							visited[x_p][y_p] = true;
							q.offer(new int[] { x_p, y_p });
						}
					}
				}
			}

			
		}

		if (result < cnt) {
			result = cnt;
		}

	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		size = Integer.parseInt(st.nextToken());
		array = new int[size][size];

		int max = -9999;
		for (int i = 0; i < size; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < size; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
				if (max < array[i][j])
					max = array[i][j];
			}
		}

		for (int b = 0; b <= max; b++) {
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (b >= array[i][j])
						array[i][j] = 0;
				}
			}
			
		
			bfs();
		}
		System.out.println(result);

	}
}

 


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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net