[백준] Level IV. 빙산

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

 

 

사용 알고리즘 

• BFS
• 구현

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    /*
        1. 4분면에 있는 0의 개수만큼 값이 줄어듬
        2. 두 덩어리로 분리되는 최초의 시간을 구함
     */
    static int n, m;
    static int [][] board;
    static int [][] tmp;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int year = 0;
    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());
        board = new int[n][m];

        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());
            }
        }
        int min = 0;
        while (year <= 1) {
            bfs();
            min++;
            if (allMelt()) {
                System.out.println(0);
                return;
            }
        }
        System.out.println(min - 1);
    }

    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        visited = new boolean[n][m];
        tmp = new int[n][m];
        year = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if (!visited[i][j] && board[i][j] != 0) { // 빙산이고, 방문하지 않은 지역
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                    year++;

                    if (year > 1) break;

                    while(!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];
                        int zero_count = 0;
                        for(int dir = 0; dir < 4; dir++){
                            int nx = x + dx[dir];
                            int ny = y + dy[dir];
                            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                            if (visited[nx][ny]) continue;
                            if (board[nx][ny] == 0) zero_count++;

                            if (board[nx][ny] != 0) {
                                queue.add(new int[]{nx, ny});
                                visited[nx][ny] = true;
                            }

                        }
                        tmp[x][y] = zero_count;
                    }
                }
            }
        }
        cal(tmp);
    }

    public static void cal(int [][] tmp) {
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                board[i][j] -= tmp[i][j];
                if (board[i][j] < 0) board[i][j] = 0;
            }
        }
    }

    public static boolean allMelt() {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
                if (board[i][j] != 0) return false;
            }
        return true;
    }
}

 

회고

 

문제를 풀면서 빙산이 두 덩어리 이상으로 분리되는 조건을 생각하느라 좀 시간이 걸렸다. 

 

기존에 생각했던 방식은 board 배열이 업데이트가 되고, 다시 bfs를 돌며 큐에 넣는 횟수가 2 이상인 경우를 메서드로 따로 뺐는데, 이렇게 하면 시간 낭비가 심할 것 같았다.

 

큐에 넣는 횟수가 2 이상인 경우를 왜 구하냐면, 방문하지 않고 빙산인 경우에만 큐에 넣어서 BFS를 돌려주고 있는데 만약 탐색이 끝나고 나서 다시 이중 포문을 돌 때 탐색을 진행한다면 이어져있지 않다는 의미가 된다. (말을 좀 어렵게 쓴듯...)

 

위에 생각했던 메서드로 따로 뺴서 BFS를 또 돌리는 형식 말고, BFS를 돌릴 때 같이 count를 계산한다면 해결되는 문제였다. 

 

그리고 year > 1 이라는 탈출 조건을 넣어야 정상적인 답을 구할 수 있다.

 

제출하고 자꾸 56퍼에서 멈추고 시간초과가 나길래 봤더니 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 이 조건을 생각못했다. 그래서 allMelt() 라는 메서드를 통해서 체크해줬더니 잘 통과했다. 

 

생각보다 그렇게 어렵지 않은 문제였다. 그런데 문제푸는 시간을 더 줄여야 할 것 같다.

 

특히, 해당 좌표에서 상하좌우 0의 갯수를 구할 때 board[nx][ny] != 0일 때, 즉 빙산일 때만 큐에 넣고 방문처리를 해줬어야 했는데 위 조건을 추가하지 않았더니 바닷물도 큐에 같이 넣어버려서 많이 꼬였다.