[코드트리/INTERMEDIATE LOW] 빙하 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• BFS

1. 빙하에 둘러쌓여 있지 않은 물들을 구해야 한다. ▷ 매번 (0,0)에서 BFS를 수행한다.

2. 완전탐색을 통해 주변에 빙하에 둘러쌓여 있지 않은 물이 있는 빙하들을 찾아 녹인다.

3. 과정 1,2를 격자 내에 빙하가 존재하지 않을 때까지 실행하며 걸리는 시간과 마지막으로 녹은 빙하의 크기를 갱신한다.

▷ 완전탐색 통해 확인

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int WATER = 0;
    static final int ICE = 1;
 
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
 
    static int N, M;
    static int[][] map;
 
    // BFS용
    static Queue<int[]> q = new ArrayDeque<>();
    static boolean[][] visited;
 
    static int time, meltCnt;    // 전부 녹는데 걸리는 시간, 마지막으로 녹은 빙하 크기
 
    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());
 
        map = new int[N][M];
        visited = new boolean[N][M];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        do {
            time++;
            meltCnt = 0;
 
            bfs();  // 빙하에 둘러쌓여있지 않은 물의 위치를 전부 방문 표시
            melt(); // 녹이기
        } while(iceExists());
 
        System.out.println(time + " " + meltCnt);
    }
 
    // (0,0)부터 빙하에 둘러쌓여 있지 않은 "물" 탐색해 방문 처리
    private static void bfs() {
        initialize();   // 방문 배열 매번 초기화
 
        q.add(new int[] {0, 0});    // 항상 (0,0)에서 시작
        visited[0][0] = true;
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(canGo(nx, ny)) {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
        }
    }
 
    // 격자 내에 있고, 방문한 적 없는 "물"인 경우 방문 표시
    private static boolean canGo(int x, int y) {
        return inRange(x, y) && map[x][y] == WATER && !visited[x][y];
    }
 
    // 주변에 빙하에 둘러쌓여 있지 않은 물이 있는 빙하 찾아 녹이는 메소드
    private static void melt() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == ICE && aroundWater(i, j)) {
                    map[i][j] = 0;
                    meltCnt++;
                }
            }
        }
    }
 
    // 주변에 빙하에 둘러쌓이지 않은 "물"이 있는지 판단하는 메소드
    private static boolean aroundWater(int x, int y) {
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(inRange(nx, ny) && visited[nx][ny])
                return true;
        }
 
        return false;
    }
    
    // 방문 배열 초기화 함수
    private static void initialize() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                visited[i][j] = false;
            }
        }
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
 
    // 격자 내에 빙하가 존재하는지 확인하는 함수
    private static boolean iceExists() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == ICE)
                    return true;
            }
        }
 
        return false;
    }
}

 

 

➕ 다른 풀이 방식

이런 방법도 있더라,,, 그냥 주변 신경 안 쓰고 bfs 수행해도 되네,,

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

public class Main {
    static int n, m;
    static int[][] board;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visited;
    static int res = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        board = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            s = br.readLine().split(" ");
            for(int j = 0; j < s.length; j++) {
                board[i][j] = Integer.parseInt(s[j]);
            }
        }
        
        int time = 0;
        
        while(true) {
            time++;
            visited = new boolean[n][m];
            
            int cnt = bfs(0, 0);
            
            if(cnt != 0) res = cnt;
            else {
                System.out.println((time - 1) + " " + res);
                break;
            }
        }
    }
    
    static int bfs(int x, int y) {
        int cnt = 0;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));

        while(!q.isEmpty()) {
            Node p = q.poll();
            visited[p.x][p.y] = true;

            for(int i = 0; i < 4; i++) {
                int nx = dx[i] + p.x;
                int ny = dy[i] + p.y;
                if(isRange(nx, ny) && !visited[nx][ny]) {
                    if(board[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny));
                    } else {
                        visited[nx][ny] = true;
                        board[nx][ny] = 0;
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }

    static boolean isRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    
    static class Node {
        int x, y;

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

 

---

💦 어려웠던 점

- bfs를 어떤 지점에 대해 수행해야할지 감을 잡지 못 했다. → "빙하에 둘러쌓여있지 않은 물들" → 가장자리는 무조건 빙하에 둘러쌓여있지 않은 물들이므로 (0,0)에서 bfs 탐색하며 방문 표시

- 빙하에 둘러쌓여 있지 않은 물이 있는 빙하를 찾는 것을 어떻게 할지에 대한 고민 (말장난 같네..ㅋㅋ) 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리