[BOJ/16946번벽부수고이동하기4] c++ / BFS

문제

벽이 있는 위치에서 이동할 수 있는 칸의 개수를 찾는 문제

 

생각

처음에 아무 생각 없이 벽이 나오면 BFS 탐색해서 개수를 찾았는데 시간초과뜸 (뜰만했음)

구글링해서 어떤 식으로 푸는지 익혔는데 이해하는데 꽤나 오래걸림

0이 나오면 BFS 탐색해서 크기를 찾고, 그룹으로 만들어놓아야 함

0칸의 개수를 저장해둘 벡터 공간, 그룹 번호를 저장해둘 배열 생성

1이 나오면 상하좌우를 확인하는데, 이때 칸이 0이면 그룹으로 묶어둔 칸 수를 더해줌

 

문제풀이

1.board 배열에서 0이 나오면 BFS탐색

1-1.BFS

-0인 칸이 나오면, vis에 그룹 번호 저장 (znum)

-vector에 cnt 푸쉬 ( 그룹번호랑 순서 맞음 / znum이랑 vector 인덱스는 같이 움직인다고 보면 편함 )

2.배열에서 1이 나오면 상하좌우 탐색

2-1.인접한 곳에 0이 있다면, set에 vis[nx][ny](그룹번호)를 insert

-set 사용 ? 상하좌우에 중복되는 그룹 번호가 존재할 수 있어서 방지하기 위함

3.정답배열의 값 + vector[set에 존재하는 그룹번호] 해줌

-for(auto a : set ) set에 있는 값을 다 순회함 / set은 인덱스로 접근 불가

4.정답배열에 3번의 값을 % 10해서 저장함

 

* 정리

배열에서 0을 찾아 bfs탐색함 / 각 그룹의 크기는 벡터에 저장해둠

배열에서 1을 찾아 상하좌우를 탐색함 / 인접한 곳에 0이 있다면 그룹번호를 통해 벡터[그룹번호]에서 0의 크기를 더해줌 ( 중복 X )

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[1001][1001];
int vis[1001][1001], ans[1001][1001];
int N, M, cnt;
int znum=1;
vector<int> Zero={};
void BFS(int a, int b) {
    queue<pair<int, int>> Q;

    Q.push({a, b});
    vis[a][b] = znum;
    cnt = 0;

    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cnt++;
        
        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( board[nx][ny] || vis[nx][ny] ) continue;

            Q.push({nx, ny});
            vis[nx][ny] = znum;
        }
    }
    
    Zero.push_back(cnt); // znum 인덱스에 0 영역크기 넣어줌
}
int main() {
    ios::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++ )
            board[i][j] = str[j] -'0';
    }
    Zero.push_back(0);
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ ) 
            if ( board[i][j] == 0 && vis[i][j] == 0 ) {
                BFS(i, j);
                znum++;
            }

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 0 ) continue;
            set<int> s;
            ans[i][j] = 1;
            for ( int dir = 0; dir < 4; dir++ ) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];

                if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
                if ( board[nx][ny] == 0 ) {
                    s.insert(vis[nx][ny]);
                }
            }

            for ( auto a : s )
                ans[i][j] += Zero[a];

            ans[i][j] = ans[i][j] % 10;

            s.clear();
        }
    }

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            cout << ans[i][j];
        }
        cout << "\n";
    }
      
}