[ 백준 16946 ] 벽 부수고 이동하기4 (C++)

백준의 벽 부수고 이동하기(16946) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에 이 문제를 보고, 맵의 있는 모든 1에서 갈 수 있는 0의 갯수를 BFS탐색을 통해서 Count후 제출했더니 시간초과에 걸렸다.

   따라서 본인은 조금 다른 방법으로 접근해보았다.

   기준이 '1'인 좌표가 아닌 '0'인 좌표로 잡고 탐색을 진행해 보았다.

  

2) 먼저, 맵에서 모든 0을 다 탐색해 주면서 서로 건너다닐 수 있는 0들끼리는 번호를 저장해주었다. 물론, 이를 저장해 주기

   위해서 맵을 하나 더 만들어 주었다. 다음과 같은 예를 보며 천천히 이해해보자.

  < 그림 1 >

   이런 맵이 있다고 생각해보자. 위의 맵에서 색깔로 표시된 0의 묶음들에 집중하자. 같은 색깔로 묶인 0들은 서로 건너다닐 수

   있는 놈들이다. 본인은 모든 0을 탐색하면서 각 묶음별로 0번부터 순서대로 번호를 새겨주었다. 그 번호를 저장한 맵을

   본다면 아래와 같은 형태일 것이다.

   < 그림 2 >

   이렇게 0번부터 2번까지 번호로 표시되었음을 확인할 수 있다. 또한, 각 번호별 0의 갯수들을 탐색을 하면서 Count해 주었고

   그 Count한 결과를 Vector(본문 : vector<int> Zero_Area_Size)에 저장해주었다.

   즉, Vector에는 3, 3, 1 이라는 값이 순차적으로 저장되어 있을 것이다.

  

   이후에 이제 1인 놈들을 기준으로 탐색이 시작된다.

   '1'인 좌표를 찾으면, 그 1의 좌표를 기준으로 상하좌우 총 4방향을 탐색한다.

   탐색하는 과정에서 0이 나온다면, 그 0의 갯수만큼을 더해주었다. 말보다는 그림으로 이해해보자.

  

    이해를 돕기 위해서 맵에 들어가는 숫자에 표시를 해 주었다.

    0 뒤에 있는 괄호 안에 있는 숫자는 각 0의 영역 번호이다. 쉽게 생각해서 위의 그림1과 그림2를 합쳐놓은 형태라고 생각하면

    된다.

    그렇다면 여기서, 유독 눈에 띄게 크고 기울어져있는 (1,1)에 존재하는 '1'에 주목해보자.

    저 '1'을 기준으로 상하좌우를 탐색한다면 총 3번의 0을 만나게 된다.

    0 번 소속인 (0, 1)에 존재하는 0, 0번 소속인 (1, 2)에 존재하는 0, 1번 소속인 (2, 1)에 존재하는 0 이렇게 총3개 !

    상하좌우 순서로 탐색을 한다고 가정했을 때, 가장 먼저 만나는 0은 (0, 1)에 존재하는 0번 소속의 0을 만나게 될 것이다.

    우리는 이미 0번에 소속되어 있는 0의 갯수를 알고 있다. 이전에 Vector에서 미리 Count해서 저장해 주었기 때문이다.

    그렇다면, 해당 번호에 저장되어있는 갯수를 Vector에서 불러와서 + 시켜준다.

    즉, 저 1에서 '상'방향으로 탐색을 한번 했지만, 우리는 갈 수 있는 0인 칸이 총 3칸이라는 것을 알게 되는 것이다.

    그렇다면 그 다음 탐색 방향인 '하'로 가보자.

    '하'로 가게되면 1번 소속인 0을 만나게 될 것이다. 우리는 1번 소속인 0의 갯수 또한 알고 있다.

    그렇다면 그대로 또 저장되어 있는 갯수를 +시켜서, '상','하' 두 방향 탐색만으로 6개(3 + 3)의 0인 칸을 갈 수 있음을

    알 수 있게 된다.

    '좌'로 탐색하면 1이기 때문에 Pass. 마지막 '우' 방향을 탐색해보자.

    0번 소속의 0을 만나게 된다. 하지만 이 경우에 또 "어 ? 0이네? 0번소속? 3개네 !  + 3 !" 을 해버리면 될까 ??

    안된다. 왜냐하면 0번소속인 0들은 이전에 이미 모두 탐색을 해버렸기 때문이다.

    즉, 우리는 "몇 번 소속의 0을 탐색" 했는지 체크해둘 필요가 있다.

    그렇다면 가장 일반적인 Visit[] 배열을 만들어서 체크를 해주면 되겠지만 맵의 최대크기는 1000x1000 이고... 0이 최대 몇 개의

    그룹이 나올지 계산을 하려면 할 수는 있겠지만 별로 하고 싶지 않았다.

    따라서 본인은 set을 사용해서 이 부분을 체크해 주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<set>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Area_Num[MAX][MAX];
int Zero_Area_Num;
int Answer[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<int> Zero_Area_Size;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j] - '0';
        }
    }
    memset(Area_Num, -1, sizeof(Area_Num));
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    int Cnt = 1;
    Area_Num[a][b] = Zero_Area_Num;
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 0 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Area_Num[nx][ny] = Zero_Area_Num;
                    Q.push(make_pair(nx, ny));
                    Cnt++;
                }
            }
        }
    }
    Zero_Area_Size.push_back(Cnt);
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 0 && Visit[i][j] == false)
            {
                BFS(i, j);
                Zero_Area_Num++;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 1)
            {
                set<int> Search;
                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)
                        {
                            if (Search.find(Area_Num[nx][ny]) == Search.end())
                            {
                                Search.insert(Area_Num[nx][ny]);
                                Answer[i][j] = Answer[i][j] + Zero_Area_Size[Area_Num[nx][ny]];
                            }
                        }
                    }
                }
                Answer[i][j] = Answer[i][j] + 1;
                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 << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}