[Java] 백준 빙산

1. 문제분석

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

2573번: 빙산

앞서 본 치즈랑 비슷하지만 오히려 더 쉬운문제다.

1시간마다 4방향으로 바닷물과 접촉한다면 접촉한 수만큼 빙산의 크기를 1씩 낮춘다.

그 다음, 4방향으로 연결된 빙하의 개수가 2개 이상이면 그때 시간을 표시한다.

만약 시간내에 2개 이상으로 안나오면 0으로 표시한다.

 

필자는 델타탐색 + BFS로 문제를 해결했다.

녹지 않았을 때 BFS를 통해 빙하의 개수를 구하고 visited배열로 방문여부를 체크했다.

만약 빙하가 2개 이상, 0개면 break 또는 return을 해주었고 1개라면 빙하를 녹여본다.

녹이는 것은 치즈와 마찬가지로 접촉할 때 -1을 해주고 만약 빙하의 높이가 마이너스 된다면 0으로 표시한다.

 

치즈를 풀었다면 쉽게 풀 수 있는 문제다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point{
    int x,y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {

    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] map;
    static boolean[][] visited;
    static int width, height;

    static int[][] copyMap;

    public static void main(String[] args) throws IOException {
        //데이터 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        map = new int[height][width];
        copyMap = new int[height][width];

        for(int i = 0; i<height; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<width; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int time = 0;
        while(true){
            visited = new boolean[height][width];
            int iceCount = 0;
            //bfs로 탐색하며 2덩이 이상인지 확인
            for(int i = 0; i<height; i++){
                for(int j = 0; j<width; j++){
                    if(map[i][j] > 0) {
                        if(!visited[i][j]){
                            dfs(j, i);
                            iceCount++;
                        }
                    }
                }
            }
            //2덩이 이상, 또는 0개면 끝
            if(iceCount >= 2) break;
            if(iceCount == 0){
                System.out.println(0);
                return;
            }

            //배열 복사
            for(int i = 0; i<height; i++){
                if (width >= 0) System.arraycopy(map[i], 0, copyMap[i], 0, width);
            }

            time++;
            //배열의 값이 0보다 클때 탐색을 한다.
            for(int i = 0; i<height; i++){
                for(int j = 0; j<width; j++){
                    if(map[i][j] > 0) {
                        //녹은 개수 확인
                        isMelt(j, i);
                    }
                }
            }
        }
        System.out.println(time);
    }


    static void dfs(int x, int y){
        visited[y][x] = true;
        for(int i = 0; i<4; i++){
            int mx = x + dx[i];
            int my = y + dy[i];

            if(mx < 0 || my < 0 || mx >= width || my >= height) continue;
            if(visited[my][mx] || map[my][mx] == 0) continue;


            dfs(mx, my);
        }
    }
    static void bfs(int x, int y){
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x,y));
        visited[y][x] = true;

        while(!queue.isEmpty()){
            Point p = queue.poll();
            for(int i = 0; i<4; i++){
                int mx = p.x + dx[i];
                int my = p.y + dy[i];

                if(mx < 0 || my < 0 || mx >= width || my >= height) continue;
                if(visited[my][mx] || map[my][mx] == 0) continue;

                queue.add(new Point(mx, my));
                visited[my][mx] = true;
            }
        }
    }
    static void isMelt(int x, int y){
        //녹는거 확인은 델타탐색
        for(int i = 0; i<4; i++){
            int mx = x + dx[i];
            int my = y + dy[i];

            //copyMap을 해야 녹는 빙산이 안겹치고 나온다.
            if(mx < 0 || my <0 || mx >= width || my >= height) continue;
            if(copyMap[my][mx] == 0) map[y][x]--;
        }
        if(map[y][x] < 0) map[y][x] = 0;
    }
}

특별하게 볼 점은 copyMap을 사용하는 것이다.

만약 앞선 빙하가 다 녹아서 0이 버리면 그 다음 빙하를 계산할때도 포함되기 때문에 copyMap을 사용했다.

 

빙하가 2개 이상이면 break후 시간 출력, 0개면 0을 출력 후 return해준다.

 

이번에도 처음은 bfs, 나중은 dfs로 2개 구현했다.

이정도면 dfs가 거의 주력이지 않나..? 필자는 주변 빙산을 찾는 것이기 때문에 bfs를 사용했었다.

3. 마무리

문제를.. 잘못봐도 너무 잘못봤다.

필자는 처음에 8방향 탐색도 되는줄 알고 8방향으로 구현하고 빙하의 개수가 2일때만 출력인줄 알았다.

계속 6%에서 끝나길래 반례를 찾아보았고 문제를 다시 읽어보니 무조건 4방향, 2개 이상일때 출력이었다.

문제 좀 제대로 읽어야 겠다.