[백준][C++] 16946번: 벽 부수고 이동하기 4 <221>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

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

 

생각의 흐름

이번 문제를 1이 나올때마 전체 이동 가능한 칸을 직접 확이하면 시간안에 해결할수가 없다.

총 방문 가능한 칸이 1000*1000 칸이 있는데, 각 칸마다 확인하려면 1000*1000(모든 칸)*1000*1000(이동 가능한 최대 칸) 만큼 돌아야 한다. 시간안에 불가능 하다.

 

따라서 이를 해결 하는 핵심은 0의 덩어리들을 구하는 것 이다.

 

예를 들어 다음과 같은 예시가 있다고 해보자.

4 5
11001
00111
01010
10101

0의 덩어리들이 총 6개 가 있다. 다음과 같이 말이다.

각 0의 덩어리들을 방문할때마다 연결된 0의 갯수를 구한다.

초록은 2개

파랑은 3개

노랑은 1개

... 이런식으로 각 덩어리들의 수를 채크해서 저장해 둔다.

 

또한 각 0들을 구분해주기 위해 번호를 추가해준다. 다음과 같이 괄호안에 추가한 숫자를 보자.

각 0의 덩어리르 BFS로 돌면서 총 갯수를 파악한 후, 이를 vector에 추가해 둔다.

 

이후 다시 MAP을 확인하면서 1의 위치에 도달할때마다 주변 0의 덩어리들을 확인하여 해당 덩어리의 숫자를 vector에서 꺼내서 확인하면된다.

 

나의 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 1001

int N, M;
int zeroSpaceNum;
int zeroSpaceMap[MAX][MAX];
int Answer[MAX][MAX];
int MAP[MAX][MAX];
bool visited[MAX][MAX];
vector<int> vec;

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

void BFS(int x, int y) {
    int cnt = 1;
    queue<pair<int, int>> Q;
    Q.push({x, y});
    visited[x][y] = true;
    zeroSpaceMap[x][y] = zeroSpaceNum;

    while (!Q.empty()) {
        int nowX = Q.front().first;
        int nowY = Q.front().second;
        Q.pop();

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                continue;
            }

            if (!visited[nx][ny] && MAP[nx][ny] == 0) {
                visited[nx][ny] = true;
                cnt++;
                zeroSpaceMap[nx][ny] = zeroSpaceNum;
                Q.push({nx, ny});
            }
        }
    }

    vec.push_back(cnt);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = str[j] - '0';
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (MAP[i][j] == 0 && !visited[i][j]) {
                BFS(i, j);
                zeroSpaceNum++;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (MAP[i][j] == 1) {
                set<int> search;
                int canGoPath = 1;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (MAP[nx][ny] == 0 && search.find(zeroSpaceMap[nx][ny]) == search.end()) {
                            canGoPath += vec[zeroSpaceMap[nx][ny]];
                            search.insert(zeroSpaceMap[nx][ny]);
                        }
                    }
                }
                Answer[i][j] = canGoPath;
                Answer[i][j] = Answer[i][j] % 10;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << Answer[i][j];
        }
        cout << "\n";
    }

    return 0;
}