[알고리즘] 벽 부수고 이동하기 4

구현 방식

• 벽마다 체크를 하면, BFS가 O(NM) 이므로 O(N^2M^2)가 되므로, 시간이 오버된다.
• 따라서 빈공간을 그룹으로 탐색하고, 그룹에 있는 원소개수를 저장해놓는다.
• 그리고 벽마다 인접해있는 그룹의 원소 개수를 합해준다.

코드

• 최종 코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

const int MAXSIZE = 1000;

char graph[MAXSIZE][MAXSIZE] = {};
int group[MAXSIZE][MAXSIZE] = {};

pair<int,int> Directions[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

void solution(int N, int M);
int bfs(int N, int M, pair<int,int> start, int groupIdx);
bool canGo(int N,int M, pair<int,int> pos);

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            cin >> graph[i][j];
        }
    }

    solution(N,M);

    return 0;
}


void solution(int N, int M)
{
    int groupIdx = 0;
    vector<int> v;

    fill(&group[0][0], &group[MAXSIZE-1][MAXSIZE], -1);
    // make group
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(graph[i][j] == '0' && group[i][j] < 0)
            {
                v.push_back(bfs(N,M,{i,j}, groupIdx++));
            }
        }
    }

    // count 인접한 그룹
    int counter = 0;
    pair<int,int> next;

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            unordered_set<int> us;

            if(graph[i][j] == '1')
            {
                counter = 0;
                counter++;
                for(auto& dir : Directions)
                {
                    next = {i + dir.first, j + dir.second};
                    if(canGo(N,M, next))
                    {
                        us.insert(group[next.first][next.second]);
                    }
                }

                for(auto g : us)
                {
                    counter += v[g];
                }
                cout << counter % 10;

            }
            else
            {
                cout<< 0;
            }


        }
        cout << "\n";
    }





}


int bfs(int N, int M, pair<int,int> start, int groupIdx)
{
    queue<pair<int,int>> q;
    q.push(start);
    group[start.first][start.second] = groupIdx;
    int counter = 1;

    pair<int,int> curr, next;
    while(!q.empty())
    {
        curr = q.front(); q.pop();
        for(auto& dir : Directions)
        {
            next = {curr.first + dir.first, curr.second + dir.second};
            if(canGo(N,M,next) && group[next.first][next.second] < 0)
            {
                counter++;
                group[next.first][next.second] = groupIdx;
                q.push(next);
            }
        }

    }
    return counter;
}

bool canGo(int N,int M, pair<int,int> pos)
{
    if(pos.first < 0 || N <= pos.first)
        return false;
    if(pos.second < 0 || M <= pos.second)
        return false;
    if(graph[pos.first][pos.second] == '1')
        return false;
    return true;
}