[BOJ/백준] 2573 빙산 (JAVA)

링크

https://www.acmicpc.net/problem/2573

 

문제 요약

N*M 크기 배열의 각 칸에는 빙산 또는 바다(0)가 있다.

각 빙산 칸에는 빙산의 높이 정보가 주어진다.

동서남북으로 붙어있는 칸들은 서로 연결되어 있는 한 덩어리로 취급한다.

빙산의 높이는 일 년마다 동서남북 네 방향으로 바다가 접해있는 개수만큼 줄어든다.

 

처음에 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년) 구하기

 

제한

• 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다.
  • N과 M은 3 이상 300 이하이다.
• 그다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈칸을 사이에 두고 주어진다.
  • 각 칸에 들어가는 값은 0 이상 10 이하이다.
• 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다.
  • 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
• 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

 

풀이

빙산이 두 덩어리 이상으로 분리되는지 여부는 결국 영역이 두 개 이상으로 분리되는지입니다.

따라서 BFS나 DFS로 문제를 풀 수 있습니다.

 

저는 DFS로 풀었습니다.

1. 처음 주어진 배열은 무조건 한 덩어리의 빙산이므로, 빙산 개수를 카운트하지 않고 녹인다.
2. 전체 배열에 대해 0이 아닌 배열 칸을 기준으로 동서남북 방향 0의 개수를 센다. 그리고 이 값을 저장한다.
3. 빙산 녹이기
   1. 다시 배열의 처음부터 0이 아닌 칸을 기준으로, 2에서 저장했던 주변 0의 개수만큼 값을 감소시킨다.
      1. 단, 값은 음수가 될 수 없다. 최솟값 0을 넘기지 않도록 한다.
      2. 전체 배열에 대해 수행한다.
   2. 시간(년)을 1 증가시킨다.
4. 빙산 개수 카운트하기
   1. 배열에서 0 초과인 칸을 시작점으로 잡는다.
   2. 시작점을 기준으로 동서남북을 탐색한다.
      1. 값이 0 초과이고 경곗값을 넘지 않으며, 이전에 방문했던 곳이 아니라면 새로 탐색한다.
      2. 탐색할 때마다 방문 여부 표시를 남기고 더 이상 연속적으로 탐색 가능한 칸이 없을 때, 탐색이 끝난다.
   3. 다음 탐색 시작점을 찾아 배열 전체에 대해 4번 과정을 반복한다.
5. 빙산의 개수가 0개이거나 2개 이상이 아니면, 2번으로 돌아가 과정을 반복한다.
6. 조건을 만족해 반복이 끝나면, 걸린 시간(년)을 출력한다.

 

코드

🚨 [1차] - 틀림

import java.util.*;
import java.io.*;

public class Main {
    static int[][] board;
    static int[][] zeroCnt;
    static boolean[][] visited;
    static int cnt= 1;
    static int[] dirx = {1,0,-1,0};
    static int[] diry = {0,1,0,-1};
    static int n, m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        int year = 0;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while(cnt>0 && cnt<2){
            // 주변 0 개수 카운트
            zeroCnt = new int[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && zeroCnt[i][j]==0){
                        int tempCnt = 0;
                        for(int k=0; k<dirx.length; k++){
                            int nx = i+dirx[k];
                            int ny = j+diry[k];
                            if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0) tempCnt++;
                        }
                        zeroCnt[i][j] = tempCnt;
                    }
                }
            }

            // 빙산 녹이기
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && zeroCnt[i][j]>0){
                        board[i][j]=Math.max(0,board[i][j]-zeroCnt[i][j]);
                    }
                }
            }
            year++;

            // 빙산 개수 카운트
            cnt=0;
            visited = new boolean[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && !visited[i][j]){
                        cnt++;
                        dfs(i,j);
                    }
                }
            }
        }
        System.out.print(cnt==0 ? 0:year);
    }

    static void dfs(int curx, int cury){
        visited[curx][cury]=true;
        for(int i=0; i<dirx.length; i++){
            int nx = curx+dirx[i];
            int ny = cury+diry[i];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(visited[nx][ny] || board[nx][ny]==0) continue;
            dfs(nx,ny);
        }
    }
}

🏷 [문제점]

• 처음에 하나의 칸을 탐색할 때 방문 여부 표시만 해주면 1년 동안은 다시 이 칸을 탐색할 일이 없다고 생각하여 탐색과 동시에 각 칸의 값을 -1 해주었습니다.
• 하지만 이렇게 해주면 바로 옆 칸의 빙산에서 줄어들 높이를 정할 때 영향을 끼치게 됩니다!
  • ex) 간단하게 [1,2,0]에서 1을 먼저 탐색하여 1->0이 되면, 2를 탐색할 때 2 ->1이 맞지만 2->0이 돼버립니다.
• 위 코드는 우연히 주어진 예제 출력이 맞아서 제출했다가 틀렸습니다 🤣

 

🏷 [해결법]

• 0이 아닌 각 칸을 기준으로 주변 0의 개수를 카운트하여 새로운 배열에 저장한 후, 저장한 값을 바탕으로 빙산 녹이기를 진행해야 합니다.
• 아니면 주변 0의 개수를 카운트한 후 빙산이 녹은 후의 값을 새로운 배열에 저장하고, 새로운 배열을 모두 채운 후 이걸 가지고 기존 배열을 업데이트합니다.

⇒ 어쨌든 빙산을 녹이는 과정에서 새로운 배열을 사용하여, 녹은 빙산 칸이 아직 녹지 않은 빙산 칸에 영향을 주지 않도록 합니다!

 

✅ [최종]

import java.util.*;
import java.io.*;

public class Main {
    static int[][] board;
    static int[][] zeroCnt;
    static boolean[][] visited;
    static int cnt= 1;
    static int[] dirx = {1,0,-1,0};
    static int[] diry = {0,1,0,-1};
    static int n, m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        int year = 0;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while(cnt>0 && cnt<2){
            // 주변 0 개수 카운트
            zeroCnt = new int[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && zeroCnt[i][j]==0){
                        int tempCnt = 0;
                        for(int k=0; k<dirx.length; k++){
                            int nx = i+dirx[k];
                            int ny = j+diry[k];
                            if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0) tempCnt++;
                        }
                        zeroCnt[i][j] = tempCnt;
                    }
                }
            }

            // 빙산 녹이기
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && zeroCnt[i][j]>0){
                        board[i][j]=Math.max(0,board[i][j]-zeroCnt[i][j]);
                    }
                }
            }
            year++;

            // 빙산 개수 카운트
            cnt=0;
            visited = new boolean[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(board[i][j]>0 && !visited[i][j]){
                        cnt++;
                        dfs(i,j);
                    }
                }
            }
        }
        System.out.print(cnt==0 ? 0:year);
    }

    static void dfs(int curx, int cury){
        visited[curx][cury]=true;
        for(int i=0; i<dirx.length; i++){
            int nx = curx+dirx[i];
            int ny = cury+diry[i];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(visited[nx][ny] || board[nx][ny]==0) continue;
            dfs(nx,ny);
        }
    }

}

🏷 시간 복잡도

• board의 크기: `N`*`M`
• 주변 0 개수 카운트: `O(N*M)`
• 빙산 녹이기: `O(N*M)`
• 빙산 개수 카운트: `O(N*M)`
  • dfs 함수: 최대 `N`*`M`번 호출
• 최종 시간 복잡도: `O(NM)`+`O(NM)`+`O(NM)` = `O(NM)`

 

🏷 실행 속도

Time: 484 ms, Memory: 135348 KB