백준 - 23634 미안하다 이거 보여주려고 어그로 끌었다(JAVA)

bfs + disjoint_set을 이용한 문제로 개인적으로 어렵게 느껴져서 올리고자 한다.

 

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

 

 

 

설명

N X M의 0,1,2로 이루어진 지도가 주어진다(0 = 불,나무 = 1, 돌 = 2)

하루동안 불은 상하좌우로 옮겨붙으면서 나무를 태우고 불이 합쳐 질떄 크기의 합과 그때의 일 수를 출력한다.

 

접근

처음에는 https://www.acmicpc.net/problem/14868 이 문제와 같은 문제인지 알았는데 기본적으로 같지만 문제 설명에서 "불이 돌에 막혀 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기의 합을 구하면 돼."이 문장으로 더 어려워진 문제이다 P4문제 이지만 개인적으로 문명보다 더어려웠다.위 문제를 먼저 풀어보기를 권장한다.

처음에는 무슨말인지 이해가 안갔지만 다음 테스트케이스를 보고 이해가 됐다.

5 6
011112
201120
022211
111101
111111

다음 예제를 보면 돌로인해서 불이 모두 합쳐질 수 가 없는걸 볼 수 있다.

 

돌로 나누어진그룹에 번호를매겨서 HashMap을 이용해 각 그룹의 불의 개수를 세어서 put을 해주고,

일 수가 지날떄마다 각 그룹의 불이 모두 만날떄 break를 해주면 해결 가능하다.

 

코드

package bj미안하다이거보여주려고어그로끌었다_23634;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class bj미안하다이거보여주려고어그로끌었다_23634 {
    private static int N, M, answer, count;
    private static int[][] board, group;
    private static boolean[][] visited;
    private static int[] parent, size;
    private static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    private static Queue<Node> queue = new ArrayDeque<>();
    private static HashMap<Integer, Integer> map = new HashMap<>();
    private static List<Node> list = new ArrayList<>();

    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());
        board = new int[N][M];
        visited = new boolean[N][M];
        parent = new int[N * M];
        size = new int[N * M];
        group = new int[N][M];


        for (int i = 0; i < N * M; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = s.charAt(j) - '0';
                if (board[i][j] == 0) count++;
            }
        }
        init();

        int region = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0 && !visited[i][j]) {
                    queue.add(new Node(i, j));
                    group[i][j] = region;
                    visited[i][j] = true;
                    list.add(new Node(i, j));
                    grouping(region++);
                }
            }
        }

        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {
                    queue.add(new Node(i, j));
                    visited[i][j] = true;
                }
            }
        }

        while (!tc()) {
            bfs();
            answer++;
        }

        if (count == 0) System.out.println(0 + " " + 0);
        else {
            int sum = 0;
            for (Node node : list) {
                int i = node.x * M + node.y;
                sum += size[findParent(i)];
            }
            System.out.println(answer + " " + sum);
        }
    }

    private static boolean tc() {
        for (Node node : list) {
            int n = node.x * M + node.y;
            int region = group[node.x][node.y];
            if (size[findParent(n)] != map.get(region)) return false;
        }
        return true;
    }

    private static void grouping(int region) {
        int count = 0;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            if (board[x][y] == 0) count++;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] == 2 || visited[nx][ny]) continue;
                group[nx][ny] = region;
                visited[nx][ny] = true;
                queue.add(new Node(nx, ny));
            }
        }

        map.put(region, count);
    }

    private static void bfs() {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int cnt = 0;
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] != 1 || visited[nx][ny]) continue;
                board[nx][ny] = 0;
                cnt++;
                int a = x * M + y;
                int b = nx * M + ny;
                visited[nx][ny] = true;
                union(a, b);

                for (int k = 0; k < 4; k++) {
                    int nnx = nx + dx[k];
                    int nny = ny + dy[k];
                    if (nnx >= 0 && nnx < N && nny >= 0 && nny < M && board[nnx][nny] == 0) union(b, nnx * M + nny);
                }
                queue.add(new Node(nx, ny));
                count++;
            }

            int num = map.get(group[x][y]) + cnt;
            map.replace(group[x][y], num);
        }

    }

    private static void init() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] != 0) continue;
                        int a = i * M + j;
                        int b = nx * M + ny;
                        union(a, b);
                    }
                }
            }
        }
    }

    private static void union(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        if (ap != bp) {
            parent[bp] = ap;
            size[ap] += size[bp];
        }
    }

    private static int findParent(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = findParent(parent[x]);
    }

    private static class Node {
        int x, y;

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

}

 

 

후기

https://www.acmicpc.net/problem/14868 이문제는 항상 모든 불이 하나로 합쳐지지만 

23634는 돌로 막혀 그룹이 나누어 질 수 있어서 더어려웠고 코드도 더 길어진거같다.