2573 - 빙산 (Java)

 

---

 

문제

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

 

풀이

스텝은 두개로 나뉜다.

 

1. 현재 빙산개수를 확인한다.

 

2 - 1 : 빙산개수가 한개라면 녹인다.

 

2 - 2 : 빙산개수가 2개 이상이거나, 0개라면 답을 출력한다.

 

※ 빙산개수 확인

 

빙산개수를 확인하는거는 bfs 를 수행하면 된다. 방문배열을 하나 준비해두고, 0 값이 아닌 값에서 bfs 를 수행해서 값이 있는것들은 방문 체크를 하고, 빙산 개수 하나를 늘려주면 된다.

( dfs 도 되지만, 난 항상 bfs 를 선호한다. dfs는 스택 오버플로우 위험이 있으니..)

 

※ 얼음 녹이기

 

조금? 주의해야할거는 녹이는 경우다.

 

이와 같은 그래프 문제에서 기존 배열의 값을 참조해서 다음 스텝의 배열값을 만들때는

 

원본 배열이 아닌, 임시 배열을 선언해주는게 좋다.

 

그 다음 임시 배열에 각 원본 요소가 얼만큼의 값 변경이 필요한지 체크한다음, 마지막으로 원본 배열값을 변경시켜준다.

 

이 문제에도 각 칸 상하좌우에 0값이 몇 개 있는지 임시 배열에 저장한다음, 원본 배열을 변경시켜주는 방식으로 진행했다.

 

코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {

    public class Node{
        public int x;
        public int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static List<ArrayList<Integer>> iceberg = new ArrayList<>();
    public static int r;
    public static int c;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};


    public void solution() throws Exception {
        int time = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        for(int i=0; i<r; i++) {
            iceberg.add(
                    new ArrayList<>(Arrays.stream(br.readLine().split(" "))
                            .map(Integer::parseInt)
                            .collect(Collectors.toList()))
            );
        }

        int icebergCount;
        while (true) {
            icebergCount = getIcebergCount();
            if(icebergCount > 1 || icebergCount == 0) {
                break;
            }
            melting();
            time++;
        }

        if(icebergCount > 1){
            System.out.println(time);
            return;
        }

        System.out.println(0);

    }

    public void melting() {

        int[][] meltingArray = new int[r][c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(iceberg.get(i).get(j) == 0) continue;
                int meltingCount = 0;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if(nx >= 0 && nx < r && ny >= 0 && ny < c && iceberg.get(nx).get(ny) == 0){
                        meltingCount++;
                    }
                }
                meltingArray[i][j] = meltingCount;
            }
        }

        // 녹여주기
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(iceberg.get(i).get(j) - meltingArray[i][j] < 0){
                    iceberg.get(i).set(j, 0);
                    continue;
                }
                iceberg.get(i).set(j, iceberg.get(i).get(j) - meltingArray[i][j]);
            }
        }
    }

    public int getIcebergCount(){
        int count = 0;
        boolean[][] visited = new boolean[r][c];

        // bfs 를 수행해서, 몇개의 대륙이 있는지 확인한다.
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {

                // 이미 방문했거나, 0 인 경우에는 bfs 를 수행하지 않는다.
                if(visited[i][j] || iceberg.get(i).get(j) == 0) continue;

                Deque<Node> queue = new ArrayDeque<>();
                queue.addLast(new Node(i,j));
                visited[i][j] = true;

                while(!queue.isEmpty()){
                    Node currentNode = queue.removeFirst();
                    int x = currentNode.x;
                    int y = currentNode.y;

                    // 상하좌우 검색한다.
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];

                        // 범위안에 들며, 방문하지 않았으며, 값이 0이 아닌경우
                        if(nx >= 0 && nx < r && ny >= 0 && ny < c && !visited[nx][ny] && iceberg.get(nx).get(ny) != 0){
                            queue.addLast(new Node(nx, ny));
                            visited[nx][ny] = true;
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기