[BOJ 16946] 벽 부수고 이동하기 4 (Java)

BOJ 16946 벽 부수고 이동하기 4

난이도 : 골드 2

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

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

 

전략

N, M <= 1000 이므로 N*M은 최대 100만이다.

만약 1인 모든 칸에서 그래프 탐색을 시작한다면 시간초과가 발생할 것이다.

따라서 0인 칸에 대해서 먼저 탐색을 다 해놓고 1인 칸의 상하좌우에서 탐색 결과를 더해주는 방식으로 접근하였다.

 

1. 0인 칸에 대해서 bfs로 인접한 칸들의 개수를 구한다. -> blankCount[r][c]

2. 1인 칸에 대해서 상하좌우 blankCount를 더한다.

 

시행착오

4 5
11001
00111
01010
10101

위의 예시를 보자.

1의 과정이 끝난 다음에 blankCount는 다음과 같이 기록될 것이다.

 

00220

33000

30101

01010

 

이 때 map[2][1] 자리에서는 상하좌우의 blankCount를 더하게 되는데

blankCount[1][1] 과 blankCount[2][0]은 같이 이어져있으므로 한 번만 더해야 한다.

이를 구분하기 위해서 bfs를 진행하고 blankCount에 저장할 때 groupId를 지정해줬다.

 

    // 0인 위치들끼리 bfs 하여 count 에 이어진 개수 저장
    static void bfs(int r, int c) {
        Queue<Pos> q = new LinkedList<>();
        List<Pos> visiting = new ArrayList<>();
        q.offer(new Pos(r, c));

        while (!q.isEmpty()) {
            Pos pos = q.poll();
            if (visited[pos.y][pos.x]) continue;

            visiting.add(pos);
            visited[pos.y][pos.x] = true;

            for (int i = 0; i < 4; i++) {
                int nr = pos.y + dy[i];
                int nc = pos.x + dx[i];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (map[nr][nc]) continue;

                q.offer(new Pos(nr, nc));
            }
        }

        for (Pos pos : visiting) {
            blankCount[pos.y][pos.x] = visiting.size();
            blankGroupId[pos.y][pos.x] = groupCounter;
        }
        groupCounter++;
    }

이제 blankGroupId에는 다음과 같이 저장된다.

 

00110

22000

20304

05060

 

각 이어진 빈칸들은 유일한 id를 갖게 되고 벽에서 상하좌우의 blankCount를 더해줄 때 중복된 id를 더하지 않도록 하면 된다.

 

	// 1인 위치들에서 인접한 0인 위치들 계산하여 result 에 저장
    static void countBlock(int r, int c) {
        result[r][c] = 1;

        List<Integer> visitedGroup = new ArrayList<>();

        for (int i = 0; i < 4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m)
                continue;

            if (visitedGroup.contains(blankGroupId[nr][nc]))
                continue;

            result[r][c] += blankCount[nr][nc];
            visitedGroup.add(blankGroupId[nr][nc]);
        }
        result[r][c] %= 10;
    }

 

코드

package BOJ_16946;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

    static int n, m;
    // 1 -> true / 0 - > false
    static boolean[][] map;

    static boolean[][] visited;

    // 연속된 0의 개수 저장
    static int[][] blankCount;
    // 연속된 0을 그룹으로 묶어서 자신이 속한 id를 저장
    static int[][] blankGroupId;
    static int groupCounter = 1;

    static int[][] result;

    final static int[] dy = { -1, 1, 0, 0 };
    final static int[] dx = { 0, 0, -1, 1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);

        map = new boolean[n][m];
        visited = new boolean[n][m];
        blankCount = new int[n][m];
        result = new int[n][m];
        blankGroupId = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j) == '1';
            }
        }

        solution();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(result[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static void solution() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!map[i][j] && !visited[i][j])
                    bfs(i, j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j]) {
                    countBlock(i, j);
                }
            }
        }
    }

    // 1인 위치들에서 인접한 0인 위치들 계산하여 result 에 저장
    static void countBlock(int r, int c) {
        result[r][c] = 1;

        List<Integer> visitedGroup = new ArrayList<>();

        for (int i = 0; i < 4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m)
                continue;

            if (visitedGroup.contains(blankGroupId[nr][nc]))
                continue;

            result[r][c] += blankCount[nr][nc];
            visitedGroup.add(blankGroupId[nr][nc]);
        }
        result[r][c] %= 10;
    }

    // 0인 위치들끼리 bfs 하여 count 에 이어진 개수 저장
    static void bfs(int r, int c) {
        Queue<Pos> q = new LinkedList<>();
        List<Pos> visiting = new ArrayList<>();
        q.offer(new Pos(r, c));

        while (!q.isEmpty()) {
            Pos pos = q.poll();
            if (visited[pos.y][pos.x]) continue;

            visiting.add(pos);
            visited[pos.y][pos.x] = true;

            for (int i = 0; i < 4; i++) {
                int nr = pos.y + dy[i];
                int nc = pos.x + dx[i];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (map[nr][nc]) continue;

                q.offer(new Pos(nr, nc));
            }
        }

        for (Pos pos : visiting) {
            blankCount[pos.y][pos.x] = visiting.size();
            blankGroupId[pos.y][pos.x] = groupCounter;
        }
        groupCounter++;
    }

    static class Pos {
        final int y;
        final int x;

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

 

깨달은 점

이어진 공간을 묶는 유형의 그래프 문제가 꽤 있는 것 같은데, 이러한 방식으로 그룹을 구분하는 준비가 되어 있다면 훨씬 편할 것 같다.

이번 풀이에서는 간단하게 id를 저장하도록 하였는데 union-find 등을 사용할 수도 있을 것이다.