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

문제는 기존 문제 변형한 것이지만, 

이 문제의 알고리즘은 BFS, DFS이다.

BFS는 Breadth기준으로 해서 찾는 것을 말한다.

방향의 기준으로해서 모든 경우를 찾아야 한다.

즉, 문제에서는 0은 패스하고, 1인 경우는 벽을 부수고, 이동할 수 있는 칸의 개수를 10으로 나누면 된다는 것이다.

 

코드는 많이 기므로, 참고용으로만 쓰길 바란다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
int map[1000][1000];
int visited[1000][1000];
int group[1000][1000];
int groupSize[1000000];
int groupNum = 1;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<pair<int, int>> q;

void bfs(int y, int x) {
    int cnt = 1;
    q.push({y, x});
    visited[y][x] = 1;
    group[y][x] = groupNum;
    while (!q.empty()) {
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue;
            if (visited[nextY][nextX] || map[nextY][nextX]) continue;
            visited[nextY][nextX] = 1;
            group[nextY][nextX] = groupNum;
            q.push({nextY, nextX});
            cnt++;
        }
    }
    groupSize[groupNum] = cnt;
    groupNum++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;
            map[i][j] = c - '0';
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j] && !map[i][j]) {
                bfs(i, j);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j]) {
                int sum = 1;
                vector<int> v;
                for (int k = 0; k < 4; k++) {
                    int nextY = i + dir[k][0];
                    int nextX = j + dir[k][1];
                    if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue;
                    if (map[nextY][nextX]) continue;
                    if (find(v.begin(), v.end(), group[nextY][nextX]) == v.end()) {
                        v.push_back(group[nextY][nextX]);
                        sum += groupSize[group[nextY][nextX]];
                    }
                }
                cout << sum % 10;
            } else {
                cout << 0;
            }
        }
        cout << '\n';
    }
    return 0;
}

너무 기네...

ㅋㅋㅋㅋㅋㅋㅋㅋ