[백준] 2468번: 안전 영역 - JAVA

 

 

문제

 

 

 

풀이

 

높이가 가장 큰 영역을 MAX로 두고 비의 양을 1부터 반복하여 비의양별 안전영역의 수를 구하는 방법으로 풀이했다.

영역의 가로세로 크기(N)를 입력받는다.

N의 크기만큼의 Integer 2차원 배열을 생성하고 배열에 값을 입력받는다. 이중 가장 큰 값을 maxNum로 입력한다.

 

maxNum만큼 반복하며 각 비의양별 안전영역을 구한다.

비의양보다 높은 영역인 경우 안전영역이며, 인접영역이 안전영역인지 탐색한다.

새로운 안전영역을 발견할경우 count를 올린다.

각 비의양별 안전영역 개수를 비교하여 가장 큰 값을 출력한다.

 

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
    static int count;
    static int[][] map;
    static int MAX = Integer.MIN_VALUE;
    static boolean[][] visited;
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        // 지역의 가장 높은 지점
        int maxNum = 0;
        map = new int[N][N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] > maxNum) {
                    maxNum = map[i][j];
                }
            }
        }

	// 높은지점까지 반복
        for(int i = 0; i < maxNum; i++) {
            visited = new boolean[N][N];
            count = 0;
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < N; k++) {
                // 비의 양보다 높은 지점이고 방문한적이 없다면(안전영역)
                    if(map[j][k] > i && !visited[j][k]) {
                        count++;
                        visited[j][k] = true;
                        bfs(i, j, k);
                    }
                }
            }
            if(count > MAX) {
                MAX = count;
            }
        }

        System.out.println(MAX);
    }

    static void bfs(int i, int j, int k) {
        for(int l = 0; l < 4; l++) {
            int newJ = j + dx[l];
            int newK = k + dy[l];
			
            // 인접지역이 방문한적이 없고 안전영역이라면
            if(newJ >= 0 && newJ < N && newK >= 0 && newK < N && !visited[newJ][newK] && map[newJ][newK] > i) {
                visited[newJ][newK] = true;
                bfs(i, newJ, newK);
            }
        }
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.