[ 백준 16932 ] 모양 만들기 (C++)

백준의 모양만들기(16932) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 가장 쉬운 방법으로 문제를 풀어보자.

   가장 쉬운 방법이라면 아마 이렇게 접근하는 방식일 것이다.

   0에 대한 좌표들을 저장해놓고, 0을 하나씩 1로 바꿔가면서 BFS혹은 DFS탐색을 통해서 1의 갯수를 Count하는 방식이다.

   정답이 나오는데에는 문제가 없는 방법이다. 하지만 ! 시간초과를 받게 될 것이다.

   왜 시간초과가 뜨게 되는지 부터 알아보고 넘어가자.

   먼저, 이 방법으로 접근할 경우 매 탐색할 때 마다 탐색 방문에 대한 2차원배열을 초기화 시키는 과정이 필요할 것이다.

   ( 사람마다 조금씩 다를 수는 있습니다. )

   그럼 최악의 경우, 1000x1000의 맵이 주어질 것이고, 이 1000x1000 탐색을 할 때 마다, 1000x1000짜리 Visit배열을

   초기화시키는 과정에서 2초를 넘어가게 될 것이다.

   따라서 이렇게 풀이에 접근을 하면 안 될 것이다.

  

   본인이 생각한 방법은 초기 맵에서 1을 그룹으로 묶어주는 것과, 그 그룹의 크기를 미리 저장해 두는 것이다.

   예제입력1을 예시로 들어보겠다.

   예제입력 1과는 조금 다른 형태이다. 바로 '1'들을 그룹으로 묶었을 때 그룹 번호로 표시한 것이기 때문

   이다. 위의 1 3개는 입력 때 입력받은 '1'이 아닌, 그룹번호 1번을 의미한다. 밑에 '2'는 2번 그룹이라는 의미이다.

   이 그룹들의 크기는 Size라는 int형 자료를 관리하는 vector를 하나 생성해서 저장해 주었다.

   즉, Size = { 3, 1 } 이 저장되어 있을 것이다.

2) 이후에 과정을 순서대로 적어보겠다.

   1. 모든 0에서 인접한 칸을 방문해본다.

   2. 방문한 칸이 0이 아니라면, 기존에 방문했던 그룹이 아닌지 판단 한다.

   3. 기존에 방문했던 그룹이 아니라면, 해당 그룹의 크기 + 1을 하고, 중복 체크용 변수를 ++를 해준다.

   4. 최종 크기를 구한다.

   무슨 소리인지 하나도 모르겠다 내가 써놓고도

   차근차근 해보도록 하자. 위의 맵을 다시한번 가져와보겠다.

  

   여기서 빨강색 0을 기준으로 한번 위의 순서를 진행해보겠다.

   1. 인접한 칸을 방문해본다.

   - 이 과정에서 북쪽에 있는 1, 동쪽에 있는 1, 남쪽에 있는 1 을 방문하게 될 것이다.

     (편의상 동, 북, 남 순서로 방문했다고 가정해보자.)

   2. 기존에 방문했떤 그룹인지 판단한다.

   - '1'번 그룹을 이미 방문했나? 아니다. 아직 방문하지 않았다. 그렇다면 계산을 해줄 필요가 있다고 판단 !

   3. 해당 그룹의 크기 + 1을 하고, 중복 체크용 변수를 ++ 해준다.

   - 해당 그룹의 크기는 '1'번 그룹의 크기를 의미하고, Size[0]에 '3'으로 저장되어 있으므로 3 + 1한 값을 저장해주고,

     중복 체크용 변수를 ++해준다.

     그렇다면, 현재 빨강색 0을 기준으로 저장되어 있는 크기 = 4 , 중복체크용 변수 = 1 이 될 것이다.

   다시, 순서가 돌아서 북쪽을 방문했다고 생각하자.

   하지만 북쪽에 있는 1은 이미 방문했던 그룹이기 때문에 더 이상 계산하지 않는다.

   순서가 돌아서 남쪽을 방문했다고 생각해보자.

   남쪽에 있는 '2'번 그룹은 아직 방문한 적이 없기 때문에 계산을 진행한다.

   해당 그룹의 크기를 1을 하고, 중복 체크용 변수를 ++ 한다. 즉, 해당 그룹의 크기는 2가 되고, 이 값을 저장해준다.

   즉, 빨강색 0을 기준으로 저장되어 있는 기존의 값인 4에다가 이 그룹의 크기인 2를 합쳐서 저장한다.

   그럼 6이 되고, 중복체크용변수 또한 ++되어 2가 될 것이다.

  

   이후 최종계산을 진행하면 되는데, 전체 크기에서 (중복체크용 변수 - 1) 한 값을 빼주면 된다.

   왜 그럴까?? 빨강색 0이 중복되어서 크기에 계산되어 있기 때문이다.

   즉, 하나의 0을 기준으로 총 4개의 그룹이 중복계산되어있다면, 3만큼을 빼줘야하고,

   3개의 그룹이 중복되어있다면 2를 빼줘야하고, 2개의 그룹이라면 1을, 1개의 그룹이라면 0을 빼주면 된다.

   즉, 중복된 그룹의 갯수 - 1 한 값을 전체 크기에서 빼주면 된다.

   계산을 해보면 6에서 (2 - 1)을 빼면 6 - 1 이 되고 답은 5로 도달할 수 있게 된다.

   생각을 조금만 한다면 어렵지 않게 이해할 수 있을 것 같다 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, Answer = -987654321;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
vector<pair<int, int>> V;
vector<int> Size;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 0) V.push_back(make_pair(i, j));
        }
    }
}
 
int BFS(int a, int b, int Idx)
{
    queue<pair<int, int>> Q, NQ;
    Q.push(make_pair(a, b));
    NQ.push(make_pair(a, b));
 
    Visit[a][b] = true;
    int R_Value = 1;
 
    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] == 1 && Visit[nx][ny] == false)
                {
                    R_Value++;
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                    NQ.push(make_pair(nx, ny));
                }
            }
        }
    }
 
    while (NQ.empty() == 0)
    {
        int x = NQ.front().first;
        int y = NQ.front().second;
        NQ.pop();
 
        MAP[x][y] = Idx;
    }
    Size.push_back(R_Value);
    return R_Value;
}
 
void Solution()
{
    int Idx = 1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 1 && Visit[i][j] == false)
            {
                int Temp = BFS(i, j, Idx);
                Answer = Bigger(Answer, Temp);
                Idx++;
            }
        }
    }
 
 
    for (int i = 0; i < V.size(); i++)
    {
        set<int> Group_Visit;
 
        int x = V[i].first;
        int y = V[i].second;
        int Temp_Size = 0;
        int Cnt = 0;
 
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] != 0)
                {
                    if (Group_Visit.find(MAP[nx][ny]) == Group_Visit.end())
                    {
                        Group_Visit.insert(MAP[nx][ny]);
                        Temp_Size = Temp_Size + Size[MAP[nx][ny] - 1] + 1;
                        Cnt++;    // 몇 개의 그룹이랑 겹치는지 Check
                    }
                }
            }
        }
 
        Temp_Size = Temp_Size - (Cnt - 1);
        Answer = Bigger(Answer, Temp_Size);
    }
 
    cout << Answer << 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;
}