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

🔺 문제

2468번: 안전 영역

 

 

🔺 코드

◼️  BFS 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N;
    static int[][] map;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
        int minH = 0;
        int maxH = 0;
        
        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());
                
                maxH = Math.max(maxH, map[i][j]);
                minH = Math.min(minH, map[i][j]);
            }
        }
        
        int max = 0;
        for(int k = minH ; k <= maxH ; k++) {
            visited = new boolean[N][N];
            int cnt = 0;
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    if(!visited[i][j] && map[i][j] > k) {    // 안전지대 : 방문한 적 없고, ⭐원소 길이가 기준 길이 k보다 길 때⭐ BFS 수행
                        cnt++;
                        bfs(i, j, k);
                    }
                }
            }
 
            max = Math.max(max, cnt);
        }
        
        System.out.println(max);
    }
    
    private static void bfs(int a, int b, int height) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        visited[a][b] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 0 || y < 0 || x >= N || y >= N || visited[x][y])  continue;
                
                if(!visited[x][y] && map[x][y] > height) { // 방문한 적 없고, 길이가 목표값 보다 길 때 큐에 추가
                    visited[x][y] = true;
                    queue.add(new int[] {x,y});
                } 
            }
        }
    }
}

 

 

◼️  DFS 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N;
    static int[][] map;
    static boolean[][] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
        int maxH = 0;
        int minH = 0;
        
        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());
                maxH = Math.max(maxH, map[i][j]);
                minH = Math.min(minH, map[i][j]);
            }
        }
        
        int max = 0;
        for(int k = minH ; k <= maxH ; k++) {
            visited = new boolean[N][N];
            int cnt = 0;
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    if(!visited[i][j] && map[i][j] > k) {
                        cnt++;
                        dfs(i, j, k);
                    }
                }
            }
 
            max = Math.max(max, cnt);
        }
 
        System.out.println(max);
    }
    
    private static void dfs(int a, int b, int height) {
        visited[a][b] = true;
        
        for(int d = 0 ; d < 4 ; d++) {
            int x = a + dx[d];
            int y = b + dy[d];
            
            if(x < 0 || y < 0 || x >= N || y >= N || visited[x][y])  continue;
            
            if(!visited[x][y] && map[x][y] > height) {
                dfs(x, y, height);
            } 
        }
    }
}

✅ 해결 아이디어
✔ DFS / BFS
- 안전한 영역 갯수 = DFS / BFS 수행 횟수
* 안전지대 : 방문한 적 없고, ⭐원소 길이가 기준 길이 k보다 길 때

 

『방문한 적 없는 경우』 조건은 넣었는데,

『길이가 현재 길이보다 길어야 한다는 조건』을 빠뜨려서 틀렸었다...

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

으아 놓친 조건만 빨리 캐치했어도 더 빨리 풀 수 있었는데........

분발합시다.......

 

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

 

 

(+ 0125 2회독)

BFS를 사용했다.

격자를 입력받을 때 최대 길이를 구할 수 있게 했고,

길이를 1부터 최대 길이까지 돌려보면서 해당 길이보다 길이가 작은 칸은 미리 방문처리했다.

그리고 나서 방문하지 않은 칸에 대해 BFS 수행하면서 BFS 수행 횟수= 안전 영역 수를 구해서 최댓값을 갖도록 했다.

 

그리고 이 풀이에서는 최대 영역 크기의 초기값을 1로 초기화 해야 틀리지 않는다.. 안 그럼 틀림!

 

코드 확인하기

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;
    static int[][] grid;
    static boolean[][] visited;
    
    static int maxH = 1;
    static int maxArea = 1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                maxH = Math.max(maxH, grid[i][j]);
            }
        }
        
        for(int h = 1 ; h < maxH ; h++) {
            simulate(h);
        }
        
        System.out.println(maxArea);
    }
    
    private static void simulate(int height) {
        visited = new boolean[N][N];    // 매번 초기화하기
        
        // 기준 높이보다 높이가 낮은 칸들은 미리 방문 
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(grid[i][j] <= height) {
                    visited[i][j] = true;
                }
            }
        }
        
        int cnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited[i][j]) {
                    visited[i][j] = true;
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        
        maxArea = Math.max(maxArea, cnt);
    }
    
    private static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny) || visited[nx][ny])    continue;
                
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
            }
        }
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
}
 

 

---

(참고)

[BOJ] 백준 2468번 안전 영역 (Java)