[BOJ2573] 빙산 (DFS, BFS, 그래프 탐색)

 

 

---

문제링크

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

2573번: 빙산

 

문제풀이

"빙산이 2 그룹이상 나눠지지 않고 모두 다 녹았을 때는 0을 출력한다" 조건을 이해하지 못해서 시간 소비 (반성)

 

절차

1) DFS 로 빙산 그룹을 카운팅한다. 

- 이때 빙상 그룹을 2그룹 이상 나누지 못하고 0이 된 경우 경우(모두 다 녹은 경우) 0을 출력하고 종료

- 빙상을 녹여 그룹 분할 하기 위해 while문 실행

2) BFS 사용하여 초기화시 빙산 위치를 넣어주고, 방문 처리 해준다 

- 이때 빙산 주위에 바다가 몇개 인지 카운팅 후 녹인다.

3) 1~2 과정 반복

 

반례*

# 반례 1

5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

답 0 -- 그룹이 2개로 나눠지지 않고 다 녹았으므로 0 출력

 

# 반례 2
4 4
0 0 0 0
0 3 1 0
0 1 3 0
0 0 0 0

답 1

 

# 반례 3
5 7
0 0 0 0 0 0 0
0 3 3 2 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0

답 0  -- 마찬가지로 그룹이 2개 이상 나눠지지 않고, 다 녹아버리므로 0을 출력

 

참고. 기술 블로그 - 느리더라도 꾸준하게 https://steady-coding.tistory.com/17

[BOJ] 백준 2573번 : 빙산 (JAVA)

 

제출코드 

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

public class Main {
    
     static int N, M;

    static int[][] board;

    static boolean[][] visit;
    static void input() throws Exception {
        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 + 1][M + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visit = new boolean[N + 1][M + 1];
    }

    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static void melt() {
        // Multi source BFS를 사용했는데, class 선언하여 깔끔하게 처리 가능
        Queue<Integer> que = new LinkedList<>();
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(board[i][j] != 0) {
                    que.add(i);
                    que.add(j);
                    visit[i][j] = true;
                }
            }
        }

        while(!que.isEmpty()) {
            int _x = que.poll();
            int _y = que.poll();

            int seaCnt = 0;

            for(int i = 0; i < 4; i++) {
                int dx = _x + dir[i][0];
                int dy = _y + dir[i][1];

                if(dx < 1 || dy < 1 || dx > N || dy > M) continue;
                if(visit[dx][dy]) continue;

                if(board[dx][dy] == 0) {
                    seaCnt += 1;
                }
            }

            if(board[_x][_y] - seaCnt < 0) {
                board[_x][_y] = 0;
            } else {
                board[_x][_y] -= seaCnt;
            }
        }
    }

    static void grouping(int x, int y) {
        visit[x][y] = true;

        for(int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];

            if(dx < 1 || dy < 1 || dx > N || dy > M) continue;
            if(visit[dx][dy]) continue;

            if(board[dx][dy] != 0) grouping(dx, dy);
        }
    }

    static int getGroupCnt() {
        initVisit();
        int groupCnt = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(!visit[i][j] && board[i][j] != 0) {
                    grouping(i, j);
                    groupCnt += 1;
                }
            }
        }

        return groupCnt;
    }

    static void pro() {
        int ans = 0;
        int cnt = 0;
        
        // 빙하가 2개 이상 그룹으로 분리될 경우 종료
        while((cnt = getGroupCnt()) < 2) {
            if(cnt == 0) { // 그룹을 2개 이상 나누지 못하고 빙하가 녹은 경우
                ans = 0;
                break;
            }

            initVisit();
            melt();
            ans += 1;
        }

        System.out.println(ans);
    }

    static void initVisit() {
        if(visit == null) {
            visit = new boolean[N + 1][M + 1];
        } else {
            for(int i = 1; i <= N; i++) {
                Arrays.fill(visit[i], false);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}