[코드트리/INTERMEDIATE LOW] 안전 지대 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• DFS

높이를 k를 1부터 100까지 설정해 찾아보며 안전 지대를 탐색한다.

 

높이가 k일 때, 해당 칸의 값이 k보다 크고, 방문한 적 없어야만 해당 칸을 DFS로 방문할 수 있다.

 

해당 NxM 배열에서 총 DFS 수행 횟수 = 안전 지대 수이며, 이 값을 최대 영역 수와 비교한다. 이 때 기존 최대 영역 수보다 더 크다면, 최대 영역 수를 현재 안전 지대 수로 변경하고, 높이의 값도 저장한다.

 

 

💥 유의사항

최대 영역 수를 초기화 할 때 0보다 더 작은 값으로 설정해야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
 
    static int maxZoneNum = -1;    // 🔔 최대 영역 수 : 가능한 안전 영역의 최솟값이 0이므로 이렇게 초기화
    static int K = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int k = 1 ; k <= 100; k++) {
            visited = new boolean[N][M];    // 방문 배열 새로 초기화
            int cnt = 0;
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > k && !visited[i][j]) {    // k보다 크고 방문한 적 없는 경우만 방문 가능
                        visited[i][j] = true;
                        cnt++;
                        dfs(i, j, k);
                    }
                }
            }
 
            // 🔔 기존 최대 영역 수보다 클 경우, 갱신하고 인덱스 저장
            if(cnt > maxZoneNum) {
                maxZoneNum = cnt;
                K = k;
            }
        }
 
        System.out.println(K + " " + maxZoneNum);
    }
 
    private static void dfs(int x, int y, int v) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (!inRange(nx, ny) || visited[nx][ny] || map[nx][ny] <= v) continue;
 
            visited[nx][ny] = true;
            dfs(nx, ny, v);
        }
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}

 

---

💦 어려웠던 점

- 아니 로직은 다 맞게 해놓고 최대 영역 수 처음에 0으로 잘못 설정했던 거랑, 마지막에 인자 2개 바꿔서 출력해서 틀렸다..... 억울하다ㅏㅏ..

 

 

1회독	2회독	3회독	4회독	5회독
V