[백준] 2573 빙산 (JAVA)

✉️문제

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

2573번: 빙산

 

📝 접근

   이 문제를 위해서 필요한 기능은 크게 2가지이며, BFS와 DFS를 모두 이용한다.

1. 빙산의 개수를 확인하는 코드 (DFS)

2. 빙하를 녹이는 메소드 (BFS)

 

TIP ! 

배열을 선언할 때 x,y 변수명을 이용하면 더 헷갈리는 것 같다. 이 때는 row와 col 변수명을 이용하는 것이 더 편하다.

 

🗝 문제풀이

1. 빙산의 개수를 확인하는 코드 (두개의 메소드로 분리하였다.)

1-1. 이 중 for문을 돌면서 map[i][j]가 0보다 크면 DFS를 호출하여 이용하여 연결된 좌표들을 모두 체크한다.

public static int countIceberg() {
    visited = new boolean[row][col];

    int cnt = 0;
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            if(map[i][j] > 0 && !visited[i][j]) {
                DFS(i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

 

1-2. DFS를 이용하여 뭉쳐져 있는 좌표들을 모두 체크한다. (빙산 체크)

public static void DFS(int r, int c) {
    visited[r][c] = true;

    for(int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if(nr < 0 || nc < 0 || nr >= row || nc >= col) continue;

        if(map[nr][nc] > 0 && !visited[nr][nc]) {
            DFS(nr, nc);
        }
    }
}

 

2. 빙산을 녹이는 메소드

   -> 다음과 같은 상황에서 A를 먼저 방문하고 B를 방문하게 되면, A가 0이 되버리고 B는 의도치않게 불필요한 마이너스 계산이 들어갈 수 있다. 따라서 visited 추가 배열을 이용하여 방문 표시를 해서 정확한 계산이 되도록 해야한다.

 

public static void meltIceberg() {
    visited = new boolean[row][col];

    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            if(map[i][j] > 0) {
                q.offer(new Iceberg(i, j));
                visited[i][j] = true;
            }
        }
    }

    while(!q.isEmpty()) {
        Iceberg cur = q.poll();

        int cnt = 0;
        for(int i = 0; i < 4; i++) {
            int nr = cur.r + dr[i];
            int nc = cur.c + dc[i];

            if(nr < 0 || nc < 0 || nr >= row || nc >= col) continue;

            if(map[nr][nc] <= 0 && !visited[nr][nc]) {
                cnt++;
            }
        }

        map[cur.r][cur.c] -= cnt;
    }
}