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

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

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

<문제>

naive하게 구현하면 시간초과, 라벨링의 아이디어를 떠올려도 중복처리를 해야하지만,

stl을 적극적으로 사용한다면 구현이 그리 어렵진 않다.

 

이전의 "벽 부수고 이동하기"시리즈와 마찬가지로, bfs를 사용하는데, bfs로 전처리해줄것이다.

구해야 하는것은 모든 (y, x)에 대해서, 영역의 넓이와 영역의 번호가 되겠다.

영역의 넓이를 int dp[][]

영역의 번호를 int num[][]에 저장해줄 것이다. 다만, BFS의 탐색대상은 '1'이 아닌 '0'인것에 주의하자.

벽이 있는곳은 그냥 0으로 비워두면 된다. 어처피 이를 참조할일은 없다.

영역의 넓이는 1이상의 양수를 갖는다. 애초에 0이 있기에 탐색을 시작했다면, 넓이가 곧 1부터 시작하는 셈이다.

영역의 번호는 1부터 채워주었다. 영역의 번호는 이후에 set을 사용하여 중복처리를 해준다.

이미 "벽 부수고 지나가기"시리즈를 풀어봤다면, 아래의 bfs코드를 바로 봐도 이해가 될것이다.

 

 

기본적으로 입력된 a[][]

'0'에 대해서 넓이를 저장한 dp[][]

'0'에 대해서 영역의 번호를 라벨링한 num[][]

 

위 3가지를 구한셈이고, 이제 아래의 과정을 거쳐 출력하면 된다.

1. a[i][j]가 빈칸인 경우

-> 바로 '0'을 출력하고 continue

 

2. a[i][j]가 벽인 경우

-> 현재 위치(i, j)에서 상하좌우의 위치 (y, x)에 대해서,

set에 num[y][x]가 존재하지 않으며 dp[y][x]가 0이 아닌경우, 이를 누적해준다.

물론 누적시킨 후에는 set에 insert해주어야 한다.

최대 4번에 걸쳐 누적시킨 값을 ans라고 하면, (ans+1)%10을 출력하면 된다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int y, x;
} state;
int n, m, a[1001][1001], dp[1001][1001], dy[4] = {0, 1, 0, -1},
                                         dx[4] = {1, 0, -1, 0};
bool visited[1001][1001];
int num[1001][1001], numCnt;
void f(int sy, int sx) {
    vector<state> v;
    queue<state> q;
    v.clear();
    v.push_back({sy, sx});
    q.push({sy, sx});
    visited[sy][sx] = true;
    int i, cnt = 1;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 1 || visited[y][x]) continue;
            visited[y][x] = true;
            cnt++;
            v.push_back({y, x});
            q.push({y, x});
        }
    }
    for (auto& i : v) {
        dp[i.y][i.x] = cnt;
        num[i.y][i.x] = numCnt;
    }
    numCnt++;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (j = 0; j < m; j++) {
            a[i][j] = s[j] - '0';
        }
    }
    numCnt = 1;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (a[i][j] == 0 && !visited[i][j]) {
                f(i, j);
            }
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (a[i][j] == 0)
                cout << "0";
            else {
                set<int> check;
                int ans = 0;
                for (int k = 0; k < 4; k++) {
                    int y = i + dy[k];
                    int x = j + dx[k];
                    if (y < 0 || x < 0 || y >= n || x >= m) continue;
                    if (check.find(num[y][x]) == check.end()) {
                        check.insert(num[y][x]);
                        ans += dp[y][x];
                    }
                }
                cout << (ans + 1) % 10;
            }
        }
        cout << '\n';
    }
    return 0;
}