[BOJ/BFS] 백준 16946 - 벽 부수고 이동하기 4 (Java)

16946 - 벽 부수고 이동하기 4

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

문제

NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳을 나타냄
한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 하고 두 칸이 변을 공유할 때 인접하다고 함
- 벽을 부수고 이동할 수 있는 곳으로 변경
- 그 위치에서 이동할 수 있는 칸의 개수 셈
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸

입력: 첫째 줄에 N, M (1 <= N, M <= 1,000) 주어지고 다음 N개의 줄에 M개의 숫자로 맵이 주어짐
출력: 맵의 형태로 정답 출력/ 원래 빈 칸인 곳은 0, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지

---

풀이

벽마다 BFS -> 시간 초과 => 0 영역을 미리 그룹화

• `int[][] group`: 각 칸이 속한 그룹 번호
• `int[] groupSize`: 그룹 번호 -> 해당 그룹 크기

ex. `group[x][y] = 3`: (x, y)는 3번 영역/ `groupSize[3] = 12`: 3번 영역 크기 12칸

 

그룹 생성

모든 0칸 순회

int idx = 1;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == 0 && !visited[i][j]) {
            bfs(i, j, idx++);
        }
    }
}

 

BFS

(x, y)에서 시작하는 하나의 0 영역 전부 탐색

static void bfs(int x, int y, int idx) {
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{x, y});
    visited[x][y] = true;
    group[x][y] = idx;

    int cnt = 1;
    while (!q.isEmpty()) {
        int[] cur = q.poll();

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visited[nx][ny]) continue;
            if (map[nx][ny] == 1) continue;

            visited[nx][ny] = true;
            group[nx][ny] = idx;
            cnt++;
            q.offer(new int[]{nx, ny});
        }
    }

    groupSize[idx] = cnt;
}

 

벽 처리 로직

• `map[i][j] == 1`: 이 위치의 벽을 부쉈다고 가정
• 인접한 칸이 0 -> `g > 0`/ `set.add(g)`: 처음 만난 그룹만 `true` -> 중복 그룹 방지

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == 1) {
            HashSet<Integer> set = new HashSet<>();
            int sum = 1;

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                int g = group[nx][ny];
                if (g > 0 && set.add(g)) {
                    sum += groupSize[g];
                }
            }

            sb.append(sum % 10);
        } else sb.append(0);
    }
    sb.append("\n");
}

---

코드

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

// 벽 부수고 이동하기 4
public class boj_16946 {
    static int N, M;
    static int[][] map, group;
    static boolean[][] visited;
    static int[] groupSize;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static void bfs(int x, int y, int idx) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        group[x][y] = idx;

        int cnt = 1;
        while (!q.isEmpty()) {
            int[] cur = q.poll();

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (visited[nx][ny]) continue;
                if (map[nx][ny] == 1) continue;

                visited[nx][ny] = true;
                group[nx][ny] = idx;
                cnt++;
                q.offer(new int[]{nx, ny});
            }
        }

        groupSize[idx] = cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        group = new int[N][M];
        visited = new boolean[N][M];
        groupSize = new int[N * M + 1];

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

        int idx = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j, idx++);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {
                    HashSet<Integer> set = new HashSet<>();
                    int sum = 1;

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

                        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                        int g = group[nx][ny];
                        if (g > 0 && set.add(g)) {
                            sum += groupSize[g];
                        }
                    }

                    sb.append(sum % 10);
                } else sb.append(0);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}