[백준-2573]-[DFS-BFS]-빙산

문제링크 : https://www.acmicpc.net/problem/2573

---

이 문제는 낮은 합격률에 겁을 먹고 문제를 잘못 이해해서 시간을 엄청 뺏긴 문제이다. 

1년이 지나면 높이가 1이 낮아진다 하고 푸니 정말 쉽게 풀었다. 

하지만 계속해서 결과가 틀렸다 나오길래 멘붕이 왔다.

다시한번 문제를 읽어보면서 문제를 제대로 읽지 않고 코딩을 한 과거의 내가 원망스러웠다. 

이문제에서 중요하게 봐야할 문구가 두개 있다.

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 

배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

(i, j) 에 빙산이 있다 가정할때 (i-1, j), (i+1, j), (i, j-1), (i, j+1) 위치에 존재하는 0의 수만큼 빙산이 녹는다는것.

이문구를 무시하니 당연히 제출할때마다 계속 틀렸다. 

이 문제를 푸는 방법은 쉽게 두가지로 나뉜다.

• DFS로 연결여부를 확인한다.
• 빙산을 녹인다.

연결 여부는 DFS 로 확인했다.

만약 모든 빙산이 연결이 돼 있다면 한면의 DFS 호출로 모든 빙산을 접근 할 것이다.

하지만 끊어져 있다면 한번의 DFS 호출로 접근할 수 없다.

빙산이 연결 되어 있는지 확인하는 부분 소스

    public static void dfs(int y, int x, boolean[][] visited) {
        visited[y][x] = true;
        
        for(int i=0; i < 4; i++) {
            int yy = dy[i] + y;
            int xx = dx[i] + x;
            if(yy >= 0 && xx >= 0 && yy < ROW && xx < COL) {
                if(!visited[yy][xx] && iceBerg[yy][xx] > 0) {
                    dfs(yy,xx, visited);
                }
            }
        }
    }
    
    public static int getLinkedCnt() {
        int cnt = 0;
        boolean[][] visited = new boolean[ROW][COL];
        for(int i=0; i < ROW; i++) {
            for(int j=0; j < COL; j++) {
                if(iceBerg[i][j] > 0 && !visited[i][j]) {
                    dfs(i, j, visited);
                    cnt++;
                }
            }
        }
        return cnt;
    }

만약 빙산이 연결이 되어 있다면 빙산을 녹이고 연차를 1 증가시키면 된다. 

하지만 연결된 빙산이 1 이상 이면 연결이 끊어진 상태이니깐 빙산을 다시 녹일 필요 없이 종료시키면 된다.

만약 연결된 빙산이 0으로 나온다면 모든 빙산이 이미 끊어지기전에 다 녹아버렸다는 뜻이므로 year 값을 0으로 변경하고 종료시킨다.

        int year = 0;
        int linkedCnt = 0;
        
        while((linkedCnt = getLinkedCnt()) < 2) {
            // 연결된 빙산가 없으면 다 녹아버린것..
            if(linkedCnt == 0) {
                year = 0;
                break;
            }
            year++;
            // 빙산를 녹인다.
            for(int i=0; i < ROW; i++) {
                for(int j=0; j < COL; j++) {
                    if(iceBerg[i][j] > 0) {
                        copyArr[i][j] = Math.max(iceBerg[i][j] - nextYear(i, j), 0);
                    }
                }
            }
            
            // 결과를 복사한다.
            for(int i=0; i < ROW; i++) {
                for(int j = 0 ; j < COL; j++) {
                    iceBerg[i][j] = copyArr[i][j];
                }
            }
        }

빙산을 녹일때 copyArr이라는 빙산 배열과 같은 크기의 배열을 만들었다.

그 이유는 빙산을 녹일때 녹이면 안되는 빙산도 녹일수 있기 때문이다. 

바로 빙산배열에 녹인 빙산의 높이를 반영 시키면 아래와 같은 상황이 발생한다.

0	0	0	0	0
0	3	4	4	0
0	0	5	0	0
0	0	0	0	0
0	0	0	0	0

위와 같은 빙산이 존재할때 (1, 1)의 빙산의 높이는 3이고 주변에 0이 3개가 있어서 빙산의 값은 0이 된다.

바로 빙산 배열을 수정한다면 (1, 2)의 위쪽과 왼쪽이 0이기 때문에 2만큼 녹게 되는 것이다. 

이렇게 되면 정확한 연차 계산이 힘들어진다.

그래서 먼저 임시 배열에 녹는 빙산의 높이를 저장한 뒤 임시 배열의 값을 다시 빙산 배열에 반영해줘야 한다.

현재 상태의 빙산에 녹을 값을 먼저 copyArr에 값을 저장하고 이 배열을 다시 빙산 배열에 복사해야한다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    public static int ROW;
    public static int COL;
    public static int[][] iceBerg;
    public static int[][] copyArr;
    
    public static int bergCount;
    
    public static int[] dy = {-1, 1, 0, 0};
    public static int[] dx = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        ROW = Integer.parseInt(st.nextToken());
        COL = Integer.parseInt(st.nextToken());
        
        iceBerg = new int[ROW][COL];
        copyArr = new int[ROW][COL];
        
        for(int i=0; i < ROW; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < COL; j++) {
                iceBerg[i][j] = Integer.parseInt(st.nextToken());
                
                if(iceBerg[i][j] > 0) bergCount++;
            }
        }
        // 입력 및 초기화 완료
        int year = 0;
        int linkedCnt = 0;
        
        while((linkedCnt = getLinkedCnt()) < 2) {
            // 연결된 빙하가 없으면 다 녹아버린것..
            if(linkedCnt == 0) {
                year = 0;
                break;
            }
            year++;
            // 빙하를 녹인다.
            for(int i=0; i < ROW; i++) {
                for(int j=0; j < COL; j++) {
                    if(iceBerg[i][j] > 0) {
                        copyArr[i][j] = Math.max(iceBerg[i][j] - nextYear(i, j), 0);
                    }
                }
            }
            
            // 결과를 복사한다.
            for(int i=0; i < ROW; i++) {
                for(int j = 0 ; j < COL; j++) {
                    iceBerg[i][j] = copyArr[i][j];
                }
            }
        }
        
        System.out.println(year);
    }
    public static void dfs(int y, int x, boolean[][] visited) {
        visited[y][x] = true;
        
        for(int i=0; i < 4; i++) {
            int yy = dy[i] + y;
            int xx = dx[i] + x;
            if(yy >= 0 && xx >= 0 && yy < ROW && xx < COL) {
                if(!visited[yy][xx] && iceBerg[yy][xx] > 0) {
                    dfs(yy,xx, visited);
                }
            }
        }
    }
    
    public static int getLinkedCnt() {
        int cnt = 0;
        boolean[][] visited = new boolean[ROW][COL];
        for(int i=0; i < ROW; i++) {
            for(int j=0; j < COL; j++) {
                if(iceBerg[i][j] > 0 && !visited[i][j]) {
                    dfs(i, j, visited);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    public static int nextYear(int y, int x) {
        int cnt = 0;
        if(iceBerg[y][x] > 0) {
            for(int i=0; i <4; i++) {
                int yy = dy[i] + y;
                int xx = dx[i] + x;
                
                if(yy >= 0 && xx >= 0 && yy < ROW && xx < COL) {
                    if(iceBerg[yy][xx] == 0) cnt++;
                }
            }
        }
        return cnt;
    }
    
    public static void print(int year) {
        System.out.println(year + "year");
        for(int i=0; i < ROW; i++) {
            for(int j = 0 ; j < COL; j++) {
                System.out.print(iceBerg[i][j] + " ");
            }
            System.out.println("");
        }
    }
}