📙[Algo] 24.04.29 알고리즘

알고리즘 문제) BOJ16946. 벽부수고 이동하기 4

문제 요약

• N*M형태의 맵이 존재
  • 0 : 이동할 수 있는 곳
  • 1 : 이동할 수 없는 벽
• 한 칸에서 다른 칸으로 이동하려면 인접할 것
  • 인접 한다 : 변을 공유할 때
• 이때, 각 벽에대해서 다음을 구하려고함
  • 해당 벽을 부순다.
  • 그 위치에서 방문할 수 있는 칸의 개수 세기

시간 제한

• 2초

입력

• 첫째 줄에 N, M이 주어짐
  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000
• N개의 줄에 N개의 숫자로 맵이 주어짐

출력

• 맵의 형태로 출력
  • 원래 빈칸인 곳은 0, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지로 출력

접근법

• 이거는 단순히 벽이 있는 공간에서 bfs를 돌려주면 되지 않을까? 생각하면 시간초과가 뜬다. N과 M이 1000까지 가능하기 때문에
• 그래서 어떻게 푸는게 좋을까 고민하다가,
  • disjoint set 알고리즘을 사용하기로 했다.
  • 먼저 2차원 배열을 1차원으로 펼친다. map[i][j]
    • 인덱스 : M(열크기)*i + j + 1
  • 그리고 인접한 0끼리 같은 연결요소로 묶고, 해당 연결요소의 노드 사이즈를 저장한다.
  • 예를 들어, N이 4, M이 5인 map에서 아래와 같이 케이스가 주어진다면

• • (1,0), (1,1), (2,0)이 0으로 인접한 상태이니까, 연결요소를 하나로 묶어서 parent[6] = parent[7] = parent[10] = 6 인 연결요소로 묶는 것이다.

• • 마찬가지로, (0,2), (0,3)도 0으로 인접한 상태니까, 같은 연결요소로 묶는다.
  • 이때 만약 (0,1)인 벽을 부순다면 인접한 연결요소 2개의 크기 + 1(자기 자신)이 이동할 수 있는 칸의 수가 되므로 총 6칸을 이동할 수 있다.
  • 연결요소 크기는 union함수에서 parent배열의 루트 노드를 수정하면서, size배열도 함께 갱신한다. (합쳐질 부모 노드의 연결 요소 크기에 합쳐지는 노드의 현재까지 연결요소의 크기를 더함)
• 주의할 점
  • 만약 인접한 0들이 모두 같은 연결요소로 이어져있다면 인접한 연결요소 크기들 합을 더했다 중복해서 더해질 수 있다. → set을 사용해서 미리 연결요소들의 부모노드들을 저장했고, 이미 set에 존재하는 경우라면 계산하지 않았다.
    • 원해는 visited 배열로 했는데, 매번 false로 갱신해야해서 시간초과가 떴음

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[] parent;
    static int[] size;
    static boolean[] visited;
    static int[] delR = {0, 0, 1, -1};
    static int[] delC = {1, -1, 0, 0};

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
        size[a] += size[b];
    }

    static void dfs(int row, int col) {

        int mr, mc, v1 = M * row + col + 1, v2;
        visited[v1] = true;
        for (int dir = 0; dir < 4; dir++) {
            mr = row + delR[dir];
            mc = col + delC[dir];

            if (mr < 0 || mc < 0 || N <= mr || M <= mc) continue;

            v2 = M * mr + mc + 1;
            if (visited[v2] || map[mr][mc] > 0) continue;

            if (find(v1) == find(v2)) continue;

            union(v1, v2);

            dfs(mr, mc);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }

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

        size = new int[N * M + 1];
        Arrays.fill(size, 1);

        visited = new boolean[N * M + 1];

        // 인접한 0끼리 같은 연결요소로 묶고 사이즈 갱신
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 || visited[M * i + j + 1]) continue;

                dfs(i, j);
            }
        }

        // 벽마다 이동가능한 칸의 개수 구하기 => 인접한 연결요소들의 크기 + 1(자기자신)
        int sum, mi, mj, v;
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) continue;

                sum = 1;
                for (int dir = 0; dir < 4; dir++) {
                    mi = i + delR[dir];
                    mj = j + delC[dir];

                    if (mi < 0 || mj < 0 || N <= mi || M <= mj) continue;

                    if (map[mi][mj] != 0) continue;

                    v = M * mi + mj + 1;
                    if (set.contains(find(v))) continue;

                    set.add(find(v));
                    sum += size[find(v)];
                }

                set.clear();
                map[i][j] = sum;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(map[i][j] % 10);
            }
            sb.append("\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}