[백준] 16946. 벽 부수고 이동하기 4

문제 링크

[백준] 16946. 벽 부수고 이동하기 4

풀이 과정

BFS 탐색과 플러드 필(Flood Fill) 기법을 사용해 문제를 풀었습니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (visit[i][j] || map[i][j] == 1) continue;
        bfs(i, j);
        groupId++;
    }
}

먼저 0으로 표현된 빈 공간에 한해 bfs 탐색을 실행합니다.

static void bfs(int x, int y) {
    Queue<int[]> queue = new LinkedList<>();
    visit[x][y] = true;
    queue.add(new int[]{x, y});

    while (!queue.isEmpty()) {
        int[] now = queue.poll();

        group[now[0]][now[1]] = groupId;

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

            if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == 1) continue;

            visit[nx][ny] = true;
            queue.add(new int[]{nx, ny});
        }
    }
}

bfs 메소드는 인접한 빈 공간을 찾아 2차원 배열 group 에 전역변수 groupId 를 마킹합니다. 예를 들어, 문제의 두 번째 입력 예시는, bfs 메소드를 거치면 아래와 같은 배열이 만들어집니다.

groupCnt = new int[groupId];

for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        groupCnt[group[i][j]]++;

이제 위에서 만든 group 배열을 통해 groupCnt 배열 요소를 채워 넣습니다. groupCnt 는, 가장 높은 그룹 번호 크기의 1차원 배열이며, 각 그룹 번호가 마킹된 칸의 개수를 세어 저장합니다.

StringBuilder answer = new StringBuilder();

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == 0) answer.append(0);
        else answer.append(set(i, j) % 10);
    }
    answer.append("\n");
}

이제, StringBuilder 객체에 각 좌표에 해당하는 값을 하나씩 누적시켜 답의 형태를 만듭니다. 이 때, 각 좌표에 해당하는 곳이 빈 공간인 경우는 0을, 벽인 경우는 set 메소드를 호출한 결과를 10으로 나눈 나머지를 이어 붙입니다.

static int set(int x, int y) {
    int cnt = 0;
    HashSet<Integer> set = new HashSet<>();

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

        if (!inRange(nx, ny) || group[nx][ny] == 0) continue;
        set.add(group[nx][ny]);
    }

    for (int groupId : set)
        map[x][y] += groupCnt[groupId];

    return map[x][y];
}

set 메소드는 벽에 인접한 상하좌우 네 곳이 빈 공간인지를 확인하고, 빈 공간인 경우 그룹 번호를 Set 자료구조에 중복없이 저장합니다. 검사가 끝나면, Set 을 순회하며 해당 그룹 번호로 마킹된 곳의 개수를 모두 map 의 해당 좌표에 누적시킵니다.

아래 그림과 같이 (2, 1) 좌표의 벽의 경우, 상하좌우 네 곳 모두 빈 공간입니다. 왼쪽과 위는 그룹번호 2의 공간이며, 오른쪽은 3, 아래는 5입니다. 이 번호을 인덱스로, 이전에 개수를 저장해둔 groupCnt 배열을 접근해 그 개수를 파악해 각각을 map 배열에 누적시킵니다.

코드

import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visit;
    static int[][] group;
    static int groupId;
    static int[] groupCnt;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        visit = new boolean[N][M];
        group = new int[N][M];
        groupId = 1;

        for (int i = 0; i < N; i++) {
            String s = sc.next();
            for (int j = 0; j < M; j++)
                map[i][j] = s.charAt(j) - '0';
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j] || map[i][j] == 1) continue;
                bfs(i, j);
                groupId++;
            }
        }

        groupCnt = new int[groupId];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                groupCnt[group[i][j]]++;

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) answer.append(0);
                else answer.append(set(i, j) % 10);
            }
            answer.append("\n");
        }

        System.out.println(answer);
    }

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        visit[x][y] = true;
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            group[now[0]][now[1]] = groupId;

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

                if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == 1) continue;

                visit[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
        }
    }

    static int set(int x, int y) {
        int cnt = 0;
        HashSet<Integer> set = new HashSet<>();

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

            if (!inRange(nx, ny) || group[nx][ny] == 0) continue;
            set.add(group[nx][ny]);
        }

        for (int groupId : set)
            map[x][y] += groupCnt[groupId];

        return map[x][y];
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > M - 1) return false;
        return true;
    }
}