[백준] 2468번 : 안전영역 - 자바[Java]

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

2468번: 안전 영역

 

풀이

장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해야 한다.

비가 내려서 잠기는 높이의 경우의 수마다 BFS를 수행해서 안전한 영역의 최대 개수를 구한다.

로직

1. n을 입력받는다. 

2. nxn 크기의 int형 배열 arr을 선언한다.

3. 지역의 높이 정보를 입력받고 arr에 저장한다. 이 때 가장 높은 지점의 높이를 max값에 저장한다.

4. 아무 지점도 잠기지 않으면 안전 영역의 개수는 1이므로 cnt에 1을 저장한다.

5. 비로 잠기는 지점의 최대 높이를 1부터 시작하여 max-1까지 정하여 안전 영역의 개수를 구한다.

for (int i = 1; i < max; i++) {
      cnt = Math.max(cnt, calSafeArea(n, arr, i));
}

6. 안전 영역의 최대 개수 cnt를 출력한다.

 

int calSafeArea(int n, int[][] arr, int height) : 비로 잠기는 지점의 최대 높이가 height일 때 안전 영역의 개수를 반환

	public static int calSafeArea(int n, int[][] arr, int height) {
		
		boolean[][] visited = new boolean[n][n];
		int cnt = 0;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][j] > height && !visited[i][j]) {
					visited[i][j] = true;
					cnt++;
					bfs(n, arr, height, visited, i, j);
				}
			}
		}
		
		return cnt;
	}

1) 지점의 방문 여부를 체크하는 boolean형 2차원 배열 visited 생성

2) 모든 지점을 for문으로 탐색하면서, 현재 지점이 height보다 크고 아직 방문하지 않았다면 BFS 수행

 

void bfs(int n, int[][] arr, int height, boolean[][] visited, int i, int j) : BFS를 수행

	public static void bfs(int n, int[][] arr, int height, boolean[][] visited, int i, int j) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {i, j});
		
		while(!q.isEmpty()) {
			int[] tmp = q.poll();
			
			for (int k = 0; k < 4; k++) {
				int nx = tmp[0] + dx[k];
				int ny = tmp[1] + dy[k];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] > height && !visited[nx][ny]) {
					visited[nx][ny] = true;
					q.add(new int[] {nx, ny});
				}
			}
		}
	}

1) 매개변수로 넘겨받은 위치를 큐에 저장

2) 큐에서 위치를 꺼내고, 꺼낸 위치와 인접한 4방향 영역이 안전 영역에 포함되는지 체크한다. 안전 영역에 포함되면 visited[nx][ny] 를 true로 변경하고 큐에 저장한다.

 

코드

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

public class Main {

    static int[] dx = {0, 1, 0 ,-1};
    static int[] dy = {1, 0, -1, 0};

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        int max = Integer.MIN_VALUE;

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(arr[i][j], max);
            }
        }

        int cnt = 1; //아무 지역도 물에 잠기지 않을 수도 있다.

        // i는 0이면 아무 지역도 물에 잠기지 않아 cnt가 1이므로 굳이 계산할 필요가 없다.
        for (int i = 1; i < max; i++) {
            cnt = Math.max(cnt, calSafeArea(n, arr, i));
        }


        System.out.println(cnt);

    }

    public static int calSafeArea(int n, int[][] arr, int height) {

        boolean[][] visited = new boolean[n][n];
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] > height && !visited[i][j]) {
                    visited[i][j] = true;
                    cnt++;
                    bfs(n, arr, height, visited, i, j);
                }
            }
        }

        return cnt;
    }

    public static void bfs(int n, int[][] arr, int height, boolean[][] visited, int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {i, j});

        while(!q.isEmpty()) {
            int[] tmp = q.poll();

            for (int k = 0; k < 4; k++) {
                int nx = tmp[0] + dx[k];
                int ny = tmp[1] + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] > height && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
        }
    }
}