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

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int N, M;
int arr[1001][1001];        // 맵 정보
int check[1001][1001];      // 방문 여부 체크 및 방 번호
int roomSize[1001][1001];   // 각 칸이 포함된 방의 크기

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

bool canMove(int y, int x);
void findRoom(int sy, int sx, int c);
int breakWall(int y, int x);

// 해당 칸으로 움직일 수 있는가?
bool canMove(int y, int x) {
    return y >= 0 && y < N && x >= 0 && x < M && arr[y][x] == 0;
}

// 이동 가능한 칸(방)의 크기 구하기
void findRoom(int sy, int sx, int c) {
    queue <pair<int, int>> q, save;
    int cnt = 1;

    q.push({ sy, sx });
    save.push({ sy, sx });
    check[sy][sx] = c;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

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

            if (canMove(ny, nx) && check[ny][nx] != c) {
                q.push({ ny, nx });
                save.push({ ny, nx });
                check[ny][nx] = c;
                cnt++;
            }
        }
    }

    // 방을 이루는 각 칸에 방의 크기 표시하기
    while (!save.empty()) {
        int y = save.front().first;
        int x = save.front().second;
        save.pop();

        roomSize[y][x] = cnt;
    }
}

// 벽을 부수면 이동할 수 있는 칸이 몇개인가?
int breakWall(int y, int x) {
    unordered_set<int> room;
    int cnt = 1;

    // 벽 인접 4칸 확인하기
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (canMove(ny, nx) && room.find(check[ny][nx]) == room.end()) {
            room.insert(check[ny][nx]);
            cnt += roomSize[ny][nx];
        }
    }

    return cnt;
}

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

    // 입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < M; j++)
            arr[i][j] = s[j] - '0';
    }

    int c = 1; // 방 번호
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0 && roomSize[i][j] == 0) findRoom(i, j, c++);
        }
    }

    // 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) cout << 0; 
            else cout << breakWall(i, j) % 10;
        }
        cout << '\n';
    }

    return 0;
}

 

// 이동 가능한 칸(방)의 크기 구하기
void findRoom(int sy, int sx, int c) {
    queue <pair<int, int>> q, save;
    int cnt = 1;

    q.push({ sy, sx });
    save.push({ sy, sx });
    check[sy][sx] = c;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

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

            if (canMove(ny, nx) && check[ny][nx] != c) {
                q.push({ ny, nx });
                save.push({ ny, nx });
                check[ny][nx] = c;
                cnt++;
            }
        }
    }

    // 방을 이루는 각 칸에 방의 크기 표시하기
    while (!save.empty()) {
        int y = save.front().first;
        int x = save.front().second;
        save.pop();

        roomSize[y][x] = cnt;
    }
}

 처음에는 반복문에서 벽을 찾을 때마다 이동할 수 있는 칸의 수를 구하기 위해 bfs()를 돌렸다. 이 방법은 정답을 출력하기는 하지만 벽 하나만을 제외하고 같은 공간을 반복적으로 탐색하기에 비효율적이라 시간 초과가 발생하였다. 

 그래서 효율적으로 탐색을 하기 위해 미리 벽이 아닌 공간의 크기를 bfs로 구하도록 했다. 위의 함수를 호출하면 호출한 칸이 포함된 구역의 크기를 구할 수 있으며, 그 구역을 이루는 모든 칸에 방 번호와 방의 크기에 대한 정보를 부여해준다.

 

// 벽을 부수면 이동할 수 있는 칸이 몇개인가?
int breakWall(int y, int x) {
    unordered_set<int> room;
    int cnt = 1;

    // 벽 인접 4칸 확인하기
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (canMove(ny, nx) && room.find(check[ny][nx]) == room.end()) {
            room.insert(check[ny][nx]);
            cnt += roomSize[ny][nx];
        }
    }

    return cnt;
}

 함수를 호출한 칸에 위치한 벽을 부쉈을 때 이동 가능한 칸의 크기를 return하는 함수이다. 벽을 부쉈으므로 그 자리에 공간이 발생하기에 cnt는 1로 초기화한다. 또한 시작점에 인접한 상하좌우의 4개 칸을 확인하고, 그 칸이 이동 가능한 칸이라면 그 칸이 포함된 방 또한 모두 이동 가능한 칸이 되므로 cnt에 크기를 더한다. 이때 room에 방번호가 존재한다면 이미 cnt에 값을 더한 것이므로 중복으로 더하는 것을 막기 위해 if문으로 조건을 달았다.

 

    // 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) cout << 0; 
            else cout << breakWall(i, j) % 10;
        }
        cout << '\n';
    }

 답을 출력하는 부분의 코드이다. 방문한 칸이 0이라면 0을 출력하고, 1이라면 breakWall()을 통해 얻은 값에 %10연산을 한 값을 출력하도록 했다.