백준 2573번 빙산(JAVA) - BFS/DFS

백준 2573번 빙산

 

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

2573번: 빙산

 

 

문제설명

- 빙산들의 정보가 주어지고 1년 마다 빙하가 녹는다.

- 빙산은 자기의 위치를 기준으로 동서남북 사방의 방향의 0(바다)의 개수 만큼 높이가 줄어든다.

- 동서남북 방향으로 붙어있는 칸들은 연결되어 있다고 판단하고, 시간이 지남에따라 빙산이 녹아서 없어질 때 빙산의 영역(덩어리의 개수)가 2개 이상이 되는 최초의 시간을 구하는 문제. (단 2덩어리 이상이 만들어지지 않는다면 0 리턴)

 

 

 

접근

BFS로 접근

 

코드

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;

public class Main {
    static int n, m;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    static boolean[][] visit;

    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];
        visit = 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());
            }
        }

        int answer = 0;

        while (true) {
            if (bfsCnt(map) == 0) {
                answer = 0;
                break;
            }
            if (bfsCnt(map) >= 2) {
                break;
            }
            bfs();
            answer++;
        }
        System.out.println(answer);

    }

    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] != 0) {
                    q.offer(new int[]{i, j});
                    visit[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int x = temp[0];
            int y = temp[1];

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

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visit[nx][ny]) continue;
                if (map[nx][ny] == 0) {
                    if (map[x][y] > 0)
                        map[x][y]--;
                }

            }
        }
    }

    static int bfsCnt(int[][] maps) {
        int ans = 0;
        boolean[][] chk = new boolean[n][m];

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maps[i][j] != 0 && !chk[i][j]) {
                    queue.offer(new int[]{i, j});

                    while (!queue.isEmpty()) {
                        int[] tmp = queue.poll();
                        int tx = tmp[0];
                        int ty = tmp[1];

                        for (int d = 0; d < 4; d++) {
                            int nx = tx + dx[d];
                            int ny = ty + dy[d];

                            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                            if (maps[nx][ny] == 0 || chk[nx][ny]) continue;
                            queue.offer(new int[]{nx, ny});
                            chk[nx][ny] = true;
                        }
                    }
                    ans++;
                }
            }
        }


        return ans;
    }
}

 

풀이

1. 수평,수직으로 움직일 dx,dy선언

2. 빙산의 정보를 받을 map, 방문여부를 담을 visit 선언

3. 행과열 크기 받고 빙산의 정보를 입력받는다.

4. 정답을 담을 answer 선언.

5. while문을 계속해서 돌며  bfsCnt로 덩어리 개수를 체크, 빙산이 두덩어리 이상이 되거나 덩어리가 없다면 break

6. 그렇지 않다면 bfs 함수를 호출하고 answer(시간)을 증가

7. bfs함수에서는 빙산이 녹는과정을 구현 0이 아닌 곳을 전부 큐에 넣고 방문처리를 한다.(큐의 앞에 먼저 들어가서 처리된 빙산이 녹아서 0이 될 경우 다음 빙산이 바다로 인식할수 있기 때문에 visit으로 방문여부를 체크하여 원래 바다가 아니었다는것을 체크한다.)

8. 만약 방문되지 않고 0이라면 -> 빙하가 녹기전 바다라면 값이 1이상 일경우 0의개수(바다)만큼 마이너스 해준다.

9. bfsCnt는 빙산의 덩어리 개수를 체크.

 

유의사항

처음 구현할 때 모든 빙산은 같은 시간에 처리되어야 하기 때문에 앞에 처리된 빙산을 바다로 인식하지 않기위한 배열을 하나 선언한후 map을 복사해서 사용하였는데 굳이 이럴필요없이 visit을 통해 방문여부로 체크 하면 된다. 또한, 동시에 처리 되야해서 큐에 한번에 넣어두고 처리하면 된다.