[BOJ] 백준 2573번 : 빙산 (JAVA)

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

2573번: 빙산

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

 

풀이

DFS와 BFS를 활용하여 풀어야하는 문제였습니다. 먼저, 중심 로직은 아래와 같습니다.

1. 빙산이 한 덩어리일 경우 빙하를 녹인다.

2. 두 덩어리 이상 나누어지기 전에 빙하가 전부 녹아버린다면 0을 출력한다.

3. 두 덩어리 이상 나누어졌다면, 빙하를 그만 녹이고 반복 횟수를 출력한다.

4. 여전히 한 덩어리라면, 1번 과정으로 되돌아간다.

로직 자체는 단순합니다. 다만, 그 속에서 메소드를 구현하는 부분이 DFS와 BFS를 잘 다루어야할 수 있어야했기때문에 정답률을 낮게 만든 것 같습니다.

 

주요 함수 설명

1. 빙하가 몇 덩어리로 분리되었는지 계산하는 함수

    // 빙하가 분리된 개수를 구하는 함수.
    public static int SeparateNum() {
        boolean[][] 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] != 0 && !visited[i][j]) {
                    DFS(i, j, visited); // DFS 방식을 통해 총 몇개의 빙하로 나누어졌는지 구할 수 있음.
                    cnt++;
                }
            }
        }
        return cnt;
    }

위와 같이 boolean 타입 visited 배열을 형성한 뒤, 깊이 우선 방식인 DFS를 활용하면 분리된 요소가 몇 개가 있는지 쉽게 파악할 수 있습니다.

 

2. DFS

    public static void DFS(int x, int y, boolean[][] visited) {        
        visited[x][y] = true;
 
        int dx, dy;
        for (int i = 0; i < 4; i++) {
            dx = x + rangeX[i];
            dy = y + rangeY[i];
 
            if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                continue;
            }
 
            if (map[dx][dy] != 0 && !visited[dx][dy]) {
                DFS(dx, dy, visited);
            }
        }
    }

3. 빙하를 녹이는 함수 (BFS)

// 빙하를 녹이는 함수.
    public static void Melt() {
        Queue<IceBerg> q = new LinkedList<>();
 
        // visited 배열을 만드는 이유
 
        // visited 배열이 없다면,
        // 만약 1 2 가 있는 상태에서 1이 먼저 녹아서 0이 될 경우
        // 2는 녹아서 없어진 1 자리도 0이라고 판단하여
        // 필요 이상으로 더 많은 값을 녹이게 되어 버림.
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    q.offer(new IceBerg(i, j));
                    visited[i][j] = true;
                }
            }
        }
 
        int dx, dy;
        while (!q.isEmpty()) {
            IceBerg ice = q.poll();
 
            int seaNum = 0; // 빙하 상하좌우에 존재하는 바다 영역의 수.
 
            for (int i = 0; i < 4; i++) {
                dx = ice.x + rangeX[i];
                dy = ice.y + rangeY[i];
 
                if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                    continue;
                }
 
                if (!visited[dx][dy] && map[dx][dy] == 0) {
                    seaNum++;
                }
            }
 
            if (map[ice.x][ice.y] - seaNum < 0) {
                map[ice.x][ice.y] = 0;
            } else {
                map[ice.x][ice.y] -= seaNum;
            }
        }
    }

map에서 빙산이 있는 영역만을 큐에 offer하고, 하나씩 꺼내가면서 상하좌우 바다의 개수에 따라 녹이는 방식입니다. 다만, 여기서 주의해야할 점이 있습니다.

위와 같이 1과 3의 높이를 가진 빙산이 있다고 가정해 봅시다.

원래대로라면, 1년 후 빙산의 높이는 각각 0, 1이 될 것입니다. 하지만, 단순히 각 영역의 상하좌우에서 바다의 개수만을 고려해서 빙산을 녹인다고 했을 때, 1이 0이 되는 순간 3이 1에 있던 자리를 0으로 인식해 버려서 결과적으로 높이는 0이 됩니다.

이를 방지하기 위해서, 원래 빙산이 있던 자리는 visited 배열을 통해 true로 처리해 줬고, 설령 원래 있던 자리가 0이 되더라도 그것은 고려하지 않게 됩니다.

 

아래는 중심 로직과 위의 3가지 메소드를 이용해서 구현한 소스 코드입니다.

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class IceBerg {
    int x;
    int y;
 
    IceBerg(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
    static int[] rangeX = { -1, 0, 1, 0 };
    static int[] rangeY = { 0, 1, 0, -1 };
 
    static int N, M;
    static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
            }
        }
 
        int ans = 0;
        int cnt = 0;
 
        // 빙하가 2개 이상 분리될 경우 반복문을 종료.
        // 빙하가 다 녹아버렸을 경우, 0을 출력.
        while ((cnt = SeparateNum()) < 2) {
            if (cnt == 0) {
                ans = 0;
                break;
            }
 
            Melt();
            ans++;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 빙하가 분리된 개수를 구하는 함수.
    public static int SeparateNum() {
        boolean[][] 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] != 0 && !visited[i][j]) {
                    DFS(i, j, visited); // DFS 방식을 통해 총 몇개의 빙하로 나누어졌는지 구할 수 있음.
                    cnt++;
                }
            }
        }
        return cnt;
    }
 
    public static void DFS(int x, int y, boolean[][] visited) {
        visited[x][y] = true;
 
        int dx, dy;
        for (int i = 0; i < 4; i++) {
            dx = x + rangeX[i];
            dy = y + rangeY[i];
 
            if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                continue;
            }
 
            if (map[dx][dy] != 0 && !visited[dx][dy]) {
                DFS(dx, dy, visited);
            }
        }
    }
 
    // 빙하를 녹이는 함수.
    public static void Melt() {
        Queue<IceBerg> q = new LinkedList<>();
 
        // visited 배열을 만드는 이유
 
        // visited 배열이 없다면,
        // 만약 1 2 가 있는 상태에서 1이 먼저 녹아서 0이 될 경우
        // 2는 녹아서 없어진 1 자리도 0이라고 판단하여
        // 필요 이상으로 더 많은 값을 녹이게 되어 버림.
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    q.offer(new IceBerg(i, j));
                    visited[i][j] = true;
                }
            }
        }
 
        int dx, dy;
        while (!q.isEmpty()) {
            IceBerg ice = q.poll();
 
            int seaNum = 0; // 빙하 상하좌우에 존재하는 바다 영역의 수.
 
            for (int i = 0; i < 4; i++) {
                dx = ice.x + rangeX[i];
                dy = ice.y + rangeY[i];
 
                if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                    continue;
                }
 
                if (!visited[dx][dy] && map[dx][dy] == 0) {
                    seaNum++;
                }
            }
 
            if (map[ice.x][ice.y] - seaNum < 0) {
                map[ice.x][ice.y] = 0;
            } else {
                map[ice.x][ice.y] -= seaNum;
            }
        }
    }
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.