[코드트리/BFS] 빙하

문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-glacier/description?page=1&page_size=20

Code Tree | Learning to Code with Confidence

 

해결방법

해당 문제를 해결하려면 빙하에 둘러쌓여 있지 않은 물의 영역을 구하는 로직이 중요하다. 문제의 지문에 따르면 입력에서 가장자리는 모두 물 영역이라고한다. 빙하에 둘러쌓여있지 않은 물이라는 뜻은 가장자리 영역과 연결되어있어야한다는 의미이기때문에, 시작점임 0, 0에서 BFS탐색으로 도달 가능한 물 영역을 찾으면 되는 문제이다.

 

주요 로직은 BFS탐색을 하며 빙하에 둘러싸여있지 않은 물의 칸을 탐색하고, 물영역과 인접한 빙하 칸을 물 영역으로 갱신하며 카운트 하는 방식으로 구현하면 된다.

 

소스코드

import java.io.*;
import java.util.*;

class Position{
    int x, y;

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int finalCnt = 0;
    static int time = 0;
    public static void main(String[] args) throws IOException{
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        M = Integer.parseInt(first[1]);
        map = new int[N][M];
        for(int i = 0; i < N; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < M; j++){
                map[i][j] = Integer.parseInt(line[j]);
                if(map[i][j] == 1)
                    finalCnt++;
            }
        }

        int nextCnt = finalCnt;
        while(nextCnt != 0){
            finalCnt = nextCnt;
            time++;

            int[][] newMap = copyMap(map);
            Queue<Position> queue = new LinkedList<>();
            int[][] visited = new int[N][M];
            queue.add(new Position(0, 0));
            visited[0][0] = 1;
            while(!queue.isEmpty()){
                Position p = queue.poll();

                for(int i = 0; i < 4; i++){
                    Position next = new Position(p.x + dx[i], p.y + dy[i]);
                    
                    if(next.x < 0 || next.x >= M || next.y < 0 || next.y >= N)
                        continue;
                    if(newMap[next.y][next.x] == 1){
                        nextCnt--;
                        newMap[next.y][next.x] = 0;
                    }

                    if(map[next.y][next.x] == 1 || visited[next.y][next.x] == 1)
                        continue;
                    
                    visited[next.y][next.x] = 1;
                    queue.add(next);
                }
            }

            map = newMap;
        }

        System.out.println(String.format("%d %d", time, finalCnt));
    }

    static int[][] copyMap(int[][] originMap){
        int[][] newMap = new int[N][M];
        for(int i = 0; i < N; i++){
            System.arraycopy(originMap[i], 0, newMap[i], 0, M);
        }
        return newMap;
    }


}