[BaekJoon] 16946번 - 벽 부수고 이동하기 4 [Java][C++]

문제 링크

---

1. 문제 풀이

맵에 대해 벽인 경우 해당 벽을 부쉈을 때 방문할 수 있는 칸의 개수를 해당 위치에 기록해서 맵 전체에 대한 결과를 출력해야하는 문제다. 매번 벽을 부수고 BFS로 개수를 셀 경우 시간 초과가 발생하게 되는데 맵 전체를 순회하며 빈칸인 경우 인접한 모든 빈칸을 방문처리하고 가장자리 벽들을 임시로 큐에 담은 후 이를 한번에 업데이트하는 방식으로 해결했다. 이때 빈칸 덩어리의 가장자리 벽을 중복으로 세지 않기 위해 임시로 방문체크 후 방문해제를 해주는 방식으로 구현했다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int n, m;
    static char[][] grid;
    static boolean[][] visited;
    static int[][] cntGrid;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        visited = new boolean[n][m];
        cntGrid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') cntGrid[i][j] = 1;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1' || visited[i][j]) continue;

                bfs(i, j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(cntGrid[i][j] % 10);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static void bfs(int sr, int sc) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        visited[sr][sc] = true;

        int cnt = 1;

        Queue<int[]> q2 = new ArrayDeque<>();

        while (!q.isEmpty()) {
            int[] node = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (visited[nr][nc]) continue;
                if (grid[nr][nc] == '1') {
                    q2.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    continue;
                }

                q.offer(new int[]{nr, nc});
                visited[nr][nc] = true;
                cnt++;
            }
        }

        while (!q2.isEmpty()) {
            int[] node = q2.poll();
            cntGrid[node[0]][node[1]] += cnt;
            visited[node[0]][node[1]] = false;
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int n, m;
char grid[1001][1001];
bool visited[1001][1001];
int cntGrid[1001][1001];

void bfs(int sr, int sc) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    visited[sr][sc] = true;

    int cnt = 1;

    queue<pair<int, int>> q2;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (visited[nr][nc]) continue;
            if (grid[nr][nc] == '1') {
                q2.push({nr, nc});
                visited[nr][nc] = true;
                continue;
            }

            q.push({nr, nc});
            visited[nr][nc] = true;
            cnt++;
        }
    }

    while (!q2.empty()) {
        auto [r, c] = q2.front();
        q2.pop();

        cntGrid[r][c] += cnt;
        visited[r][c] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') cntGrid[i][j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1' || visited[i][j]) continue;

            bfs(i, j);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << cntGrid[i][j] % 10;
        }
        cout << '\n';
    }
}

---