[Algorithm] 99클럽 코테 스터디 10일차 TIL | 백준_빙산(2573번)

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

---

정답 안 보고 힌트 안 보고 오롯이 내 힘으로 푼 문제라 더 뿌듯!!☺️

 

복잡해 보이지만 차근차근 풀어가면 생각보다 어렵지 않다.

 

우선 덩어리의 개수를 구하는 함수가 필요하다고 생각해서 dfs 활용하였다.

map에서 덩어리(?) 개수 세는 문제는 몇 번 풀었어서 풀이가 금방 나왔다.

public static void dfs(int x, int y){
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    visited[x][y] = true;
    for(int i = 0; i < 4; i++){
        int dx_x = x + dx[i];
        int dy_y = y + dy[i];

        if(dx_x >= 0 && dx_x < N && dy_y >= 0 && dy_y < M){
            if(!visited[dx_x][dy_y] && iceberg[dx_x][dy_y] > 0){
                dfs(dx_x, dy_y);
            }
        }
    }
}
public static int countOfChunk(){
    visited = new boolean[N][M];
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(!visited[i][j] && iceberg[i][j] > 0){
                count++;
                dfs(i,j);
            }
        }
    }
    return count;
}

 

덩어리 개수는 일년마다 달라지기 때문에 빙하가 녹은 후의 결과를 계산하는 함수도 필요하다.

public static void melting(int x, int y){
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    int cnt = 0;

    for(int i = 0; i < 4; i++) {
        int dx_x = x + dx[i];
        int dy_y = y + dy[i];

        if(dx_x >= 0 && dx_x < N && dy_y >= 0 && dy_y < M){
            if(iceberg[dx_x][dy_y] == 0){
                cnt++;
            }
        }
    }
    temp[x][y] = Math.max(iceberg[x][y] - cnt, 0);
}

처음에 iceberg에 감소된 값을 그대로 넣어 값이 제대로 들어가지 않았다.

iceberg를 복사한 temp에 iceberg가 감소된 값을 넣어준다.

이때 얕은 복사 깊은 복사에 주의하여야 한다.

 

temp = iceberg 이렇게 복사를 했다가 주소값이 같아지는 얕은 복사가 되었다. 앞으로 주의하자!!

얕은 복사 깊은 복사는 아래 블로그에 잘 정리되어 있다.

https://hanyeop.tistory.com/366

[Java] 자바 1차원, 2차원 배열 복사 (얕은 복사, 깊은 복사)

 

깊은 복사를 위해 객체를 각각 복사해 준다.

iceberg = new int[N][M];
temp = new int[N][M];
for(int i = 0; i < N; i++){
    st = new StringTokenizer(br.readLine());
    for(int j = 0; j < M; j++){
        iceberg[i][j] = Integer.parseInt(st.nextToken());
        temp[i][j] = iceberg[i][j];
    }
}

 

melting 함수도 작성했고, countOfChunk 함수도 작성했으니 이제 적절히 구현 코드를 작성해 준다.

int answer = 0;

if(countOfChunk() == 1){ //빙산이 이미 분리된 경우는 검사하지 않음
    while(true){
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (iceberg[i][j] > 0) {
                    melting(i, j);
                }
            }
        }
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                iceberg[i][j] = temp[i][j];
            }
        }
        answer++;
        if(countOfChunk() == 0){ //빙산이 다 녹음
            answer = 0;
            break;
        }
        if(countOfChunk() > 1){ //빙산이 분리됨
            break;
        }
    }
}

우선 melting 함수로 빙산을 녹여주고

녹여준 결괏값을 다시 iceberg에 복사시켜 준다.

 

빙산이 다 녹아버리면 countOfChunk 값이 0이 될 것이고 이는 곧 빙산이 다 녹을 때까지 분리되지 않음을 뜻한다.

 

 

전체코드

import java.util.*;
import java.io.*;
class Main{
    static boolean[][] visited;
    static int N;
    static int M;
    static int[][] iceberg;
    static int[][] temp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        iceberg = new int[N][M];
        temp = new int[N][M];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                iceberg[i][j] = Integer.parseInt(st.nextToken());
                temp[i][j] = iceberg[i][j];
            }
        }

        int answer = 0;

        if(countOfChunk() == 1){ //빙산이 이미 분리된 경우는 검사하지 않음
            while(true){
                for(int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (iceberg[i][j] > 0) {
                            melting(i, j);
                        }
                    }
                }
                for(int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        iceberg[i][j] = temp[i][j];
                    }
                }
                answer++;
                if(countOfChunk() == 0){ //빙산이 다 녹음
                    answer = 0;
                    break;
                }
                if(countOfChunk() > 1){ //빙산이 분리됨
                    break;
                }
            }
        }
        System.out.println(answer);
    }
    public static void melting(int x, int y){
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        int cnt = 0;

        for(int i = 0; i < 4; i++) {
            int dx_x = x + dx[i];
            int dy_y = y + dy[i];

            if(dx_x >= 0 && dx_x < N && dy_y >= 0 && dy_y < M){
                if(iceberg[dx_x][dy_y] == 0){
                    cnt++;
                }
            }
        }
        temp[x][y] = Math.max(iceberg[x][y] - cnt, 0);
    }
    public static void dfs(int x, int y){
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int dx_x = x + dx[i];
            int dy_y = y + dy[i];

            if(dx_x >= 0 && dx_x < N && dy_y >= 0 && dy_y < M){
                if(!visited[dx_x][dy_y] && iceberg[dx_x][dy_y] > 0){
                    dfs(dx_x, dy_y);
                }
            }
        }
    }
    public static int countOfChunk(){
        visited = new boolean[N][M];
        int count = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(!visited[i][j] && iceberg[i][j] > 0){
                    count++;
                    dfs(i,j);
                }
            }
        }
        return count;
    }
}

 

골4를 내 힘으로 풀다니🥹

남은 기간도 홧팅