[BOJ] 16946 - 벽 부수고 이동하기 4

www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3 101 010 101

예제 출력 1

303 050 303

예제 입력 2

4 5

11001

00111

01010

10101

예제 출력 2

46003

00732

06040

50403

 

 

 

 

 

 

풀이 .

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


class Pair {
    int r, c;
    Pair(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;

    static int[][] map = null;
    static int[][] group = null;
    static int[] cntOfGroup = null;
    static boolean[][] check = null;

    static int N, M, dept, groupNum = 1;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void dfs(int r, int c) {
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(-1 < nr && nr < N && -1 < nc && nc < M) {
                if(!check[nr][nc] && map[nr][nc] == 0) {
                    check[nr][nc] = true;
                    group[nr][nc] = groupNum;
                    dept += 1;
                    dfs(nr, nc);
                }
            }
        }
    }

    public static void bfs(int r, int c) {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(r, c));

        while(!que.isEmpty()) {
            Pair p = que.poll();
            for(int i = 0; i < 4; i++) {
                int nr = p.r + rArr[i];
                int nc = p.c + cArr[i];
                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    if(!check[nr][nc] && map[nr][nc] == 0) {
                        check[nr][nc] = true;
                        group[nr][nc] = groupNum;
                        dept += 1;
                        que.add(new Pair(nr, nc));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        group = new int[N][M];
        check = new boolean[N][M];
        cntOfGroup = new int[N * M + 1];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        // 탐색 진행하며 이동 가능 경로들 그룹핑. 각 그룹의 원소의 개수 저장.
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(!check[i][j] && map[i][j] == 0) {
                    check[i][j] = true;
                    group[i][j] = groupNum;
                    dept = 1;
//                    dfs(i, j);
                    bfs(i, j);
                    cntOfGroup[groupNum] = dept;
                    groupNum += 1;
                }
            }
        }

        sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(map[i][j] == 0) {
                    sb.append("0");
                }else {  // map[i][j] == 1
                    // 상하좌우 검사하여 인접한 그룹의 그룹번호 모두 담는다
                    Set<Integer> set = new HashSet<>();
                    for(int k = 0; k < 4; k++) {
                        int nr = i + rArr[k];
                        int nc = j + cArr[k];
                        if(-1 < nr && nr < N && -1 < nc && nc < M) {
                            if(group[nr][nc] != 0 && !set.contains(group[nr][nc])) {
                                set.add(group[nr][nc]);
                            }
                        }
                    }

                    int sum = 1;  // 자기 칸까지 포함해야하므로 1로 초기화
                    for(int num : set) {  // 인접한 그룹의 cnt 모두 더함
                        sum += cntOfGroup[num];
                    }
                    sb.append(String.valueOf(sum % 10));
                }
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

벽이 있는 모든 좌표에 대해서 1 -> 0으로 바꾸고 DFS or BFS를 돌려서 하나하나 값을 구하는 방식이 먼저 떠올랐다.

시간초과가 날 것 같은 무식한 방법..

 

결국 구글링으로 해법을 확인했다. 키 포인트는 분리 집합이다.

map을 이루는 이동 가능한 덩어리를 그룹핑하고 각 그룹에 대한 좌표의 개수를 구한다. 

그 후 1인 좌표에 대해서 자신과 인접한 그룹들의 카운트를 더한 값을 출력한다.

 

알고나면 그렇게까지 어려운 해법은 아닌데 전혀 떠올리지 못했다.

이런 게 디테일이고 실력이겠지.