[BOJ] 백준 2573 - 빙산

백준 2573 - 빙산

---

이 문제는 빙산을 탐색하고, 빙산 내부의 값을 변경시키고 해당 빙산영역의 개수를 세어주는 문제입니다.

위의 문제에서 요구하는 부분은 두가지입니다.

1. 빙산을 녹인다. (빙산 근처인 상하좌우에 바다가 있는 개수만큼 빙산을 녹입니다.)

2. 빙산의 개수가 2개 이상으로 분리될 경우, 출력한다.

위의 요구하는 부분을 적용시켜 작성한 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main2573 {
    
    // 상하좌우를 보기위한 부분.
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
 
    public static void main(String[] args) throws IOException {
        // 빙산 정보 입력.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int[][] map = new int [n][m];
        for(int i=0; i<n; i++) {
            String d[] = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(d[j]);
            }
        }
        
        int cnt = 0;
        int confirm = 0;
        while((confirm = count(map)) <= 1) {
            if(confirm == 0) {
                cnt = 0;
                break;
            }
            cnt++;
            minus(map);
        }
        
        System.out.println(cnt);
    }
 
    // 빙산의 개수를 세어주는 함수.
    // dfs를 사용.
    private static int count(int[][] map) {
        // TODO Auto-generated method stub
        int cnt = 0;
        // visit 배열에 현재 값을 방문했었는 지를 저장.
        boolean[][] visit = new boolean[map.length][map[0].length];
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(!visit[i][j] && map[i][j] != 0) {
                    dfs(map, visit, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
 
    // 현재 좌표에서 상, 하, 좌, 우로 네 군데를 돌며 빙산이 있는 곳을 체크해 준다.
    private static void dfs(int[][] map, boolean[][] visit, int x, int y) {
        // TODO Auto-generated method stub
        visit[x][y] = true;
        for(int k=0; k<4; k++) {
            int rx = x + dx[k];
            int ry = y + dy[k];
            if(rx >= 0 && rx < map.length && ry >= 0 && ry < map[0].length && !visit[rx][ry] && map[rx][ry] != 0) {
                dfs(map, visit, rx, ry);
            }
        }
    }
 
    // 빙하가 있는 좌표 상, 하, 좌, 우에 바다가 접해있는 부분을 세어, 빼준다. (만약 음수가 될 경우, 0으로 바꿔준다.)
    private static void minus(int[][] map) {
        // TODO Auto-generated method stub
        boolean[][] visit = new boolean[map.length][map[0].length];
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j] == 0) continue;
                visit[i][j] = true;
                int cnt = 0;
                for(int k=0; k<4; k++) {
                    int rx = i+dx[k];
                    int ry = j+dy[k];
                    if(rx >= 0 && rx < map.length && ry >= 0 && ry < map[0].length && !visit[rx][ry]) {
                        if(map[rx][ry] == 0) cnt++;
                    }
                }
                if(map[i][j]-cnt <= 0) map[i][j] = 0;
                else map[i][j] -= cnt;
            }
        }
    }
 
}