백준 16946 벽 부수고 이동하기(c++)

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

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

BFS +DFS알고리즘을 활용하면 되지만 조건이 굉장히 까다로운 문제입니다. 벽을 부순 후 벽을 기준으로 이동할 수 있는 영역이 몇 개 인지 탐색하는 문제입니다. 이것을 일일이 탐색한다면 시간 복잡도가 O((MN)^2)으로 매우 오래 걸리게 됩니다. 그래서 이동할 수 있는 영역에 대해서 그룹을 짓고 그룹의 크기가 담겨있는 vector를 만들어 줍니다.

그리고 해당 벽을 기점으로 그룹을 세어주면 됩니다. 그러면 O(MN)으로 문

제해결을 할 수 있습니다.

 

테스트케이스를 예시로 설명 드리겠습니다.

 

입력

4 5
11001
00111
01010
10101

 다음과 같은 입력에서 벽(1)을 모두 이동할 수 있는 칸으로 만들어 줍니다(0)

그리고 0의 값을 가진 것을 BFS 탐색을 통해 그룹화해야 합니다. 

0	0	1	1	0
2	2	0	0	0
2	0	3	0	4
0	5	0	6	0

다음과 같이 그룹화하게 되면 해당 벽에서 움직일 수 있는 영역을 구할 때, BFS탐색을 통해 얻은 그룹의 크기만 더해주면 됩니다. set헤더를 이용한 이유는 해당 시점에서 그룹이 겹칠 경우를 방지하기 위해서입니다. 

0	0	1	1	0
2	2	0	0	0
2	0	3	0	4
0	5	0	6	0

해당 빨간색 부분에서 상하좌우 이동하게 되면 그룹이 2인 부분이 2개가 됩니다. 그래서 set을 이용해 그룹의 중복을 방지하였습니다. 

 

<코드>

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <tuple>
// 이동할 수 있는 빈 칸을 모두 그룹 짓고, 몇 개의 칸을 이루어져 있는지 계산
// 그룹의 크기를 모두 구하고, 각각의 벽을 빈칸으로 바꿨을 때, 최대 4개의 인접한 칸만 검사하면 됨.
// O(NM)
using namespace std;
int a[1001][1001];      // 입력
bool check[1001][1001]; // BFS 검사
int group[1001][1001];  // group[i][j], i,j의 그룹 번호
vector<int> group_size; // 해당 그룹의 개수

int mov[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m;

void bfs(int x, int y)
{
    int g = group_size.size();
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
    group[x][y] = g;
    int cnt = 1; // 자기자신 포함이기 때문에 cnt 1에서 시작

    while (!q.empty())
    {
        int r, c;
        r = q.front().first;
        c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nr = r + mov[i][0];
            int nc = c + mov[i][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m)
            {
                if (a[nr][nc] == 0 && !check[nr][nc])
                {
                    q.push(make_pair(nr, nc));
                    check[nr][nc] = true;
                    group[nr][nc] = g;
                    cnt += 1;
                }
            }
        }
    }
    group_size.push_back(cnt);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < m; j++)
        {
            a[i][j] = input[j] - '0';
            check[i][j] = false;
            group[i][j] = -1;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == 0 && !check[i][j])
            {
                bfs(i, j);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == 0)
            {
                cout << 0;
            }
            else
            {
                set<int> near;
                // 그룹 중복 방지하기 위해 set을 이용
                for (int k = 0; k < 4; k++)
                {
                    int x = i + mov[k][0];
                    int y = j + mov[k][1];
                    if (0 <= x && x < n && 0 <= y && y < m)
                    {
                        if (a[x][y] == 0)
                            near.insert(group[x][y]);
                    }
                }
                int ans = 1;
                for (int g : near)
                {
                    ans += group_size[g];
                }
                cout << ans % 10;
            }
        }
        cout << '\n';
    }

    return 0;
}