[ SWEA 2382 ] 미생물 격리 (C++)

SwExpertAcademy의 미생물격리(2382) 문제이다.

[ 문제풀이 ]

1) Vector의 Index를 이용해서 상당히 많은 부분을 해결한 문제이다. 먼저 본인은 맵을 int형 자료를 관리하는 vector로

    2차원 맵을 만들어 주었다. 2차원으로 만들어준 이유는 여러개의 군집들이 모이는 경우에, 그 군집들의 번호를 저장해주기

    위해서였다.

    이 얘기를 하기 전에 먼저 본인은 미생물들의 군집을 관리하는 구조체를 하나 만들어 주었다.

    구조체에서 관리하는 변수로는 군집의 (x, y)좌표, 그 군집에 모여있는 미생물의 수, 군집이 향하는 방향, 군집의 상태

    (죽었는지 살았는지) 로 관리해 주었다.

    이 구조체를 자료형으로 갖는 vector를 또 하나 만들어 주었다. 처음 입력받을 때 모든 군집들의 정보를 vector에 담아 주었

    다. 또한 입력과 동시에 MAP vector에 그 인덱스 번호를 넣어주었다.

void Input()    // 입력받는 함수
{
    cin >> N >> M >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y, n, d;
        cin >> x >> y >> n >> d;
        Bug Temp;
        Temp.x = x; Temp.y = y;
        Temp.Num = n; Temp.Dir = d;
        Temp.State = true;
        V.push_back(Temp);
       
        MAP[x][y].push_back(i);       

        // 해당 군집의 번호를 MAP에 push!
    }
}

  

2) 이후에는 M초가 될 때까지 움직이고 합치고 죽이는 과정을 반복해 주었다.

    먼저 움직이는 것부터 알아보자.

    군집들은 자기자신의 방향으로 한칸씩 이동하는데 본인은 정말 움직여 주기만했다. 뭐 테두리로 가거나, 합쳐지는 군집들

    고려하지 않고 움직여 주기만 했다. 단지, vector에 저장되어 있는 군집들의 (x, y)좌표를 바꿔주기만 하였고 맵의 상태만

    바꿔주었다.

    과정은 이렇다.

    1. 현재 군집이 존재하는 좌표들을 모두 없애준다.;

    2. 한칸씩 움직이면서 군집이 존재하는 좌표에 해당 군집의 번호를 넣어준다.

    말보다는 코드로 이해해보자.

void Move_Bug()
{
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;

        MAP[V[i].x][V[i].y].clear();        // 먼저 기존의 상태 제거
    }

    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;

        V[i].x = V[i].x + dx[V[i].Dir];
        V[i].y = V[i].y + dy[V[i].Dir];
        MAP[V[i].x][V[i].y].push_back(i);    // 맵의 새로운 좌표에 Index번호 push
    }
}

     이렇게 움직이고 나면 어떻게 되있을까?? 아마 2개이상의 군집이 모인 좌표의 size는 1보다 클 것이다.

      또한 맵의 테두리로 가 있는 군집들이 있을 것이다. 이제 이것들을 처리해 보자.

      먼저 첫번째는 테두리에 있는 놈들이다.

      테두리에 있는 놈들은 미생물의 수가 절반으로 줄게된다. 이 과정에서 0마리가 되면 더이상 군집은 군집의 역할을

      하지 못하게된다. 그게 아니라면 방향이 반대방향으로 전환된다.

      우리는 Vector에 모든 군집들에 대한 정보가 저장되어 있으므로 수를 절반으로 감소시켜주면 되고

      죽게되는 군집들에 대해서는 State = false 로 바꿔주면된다. 사실 군집안에 미생물의 수가 0이 되면 죽는거라서 딱히

      State가 필요하지는 않은데 왜 만들어서 썻는지 모르겠다.

     

      중요한건 합치는 부분이다. 군집들이 한 곳에 합쳐졌다는 것을 우리는 어떻게 알 수 있을까??

      아마 (x, y)에 여러군집들이 합쳐졌다고 하면 MAP[x][y].size() 가 2 이상일 것이다. 따라서, 이 경우에 여기에 모인

      군집들 중에서 가장 많은 미생물들이 있는 곳을 찾아내서 그 수만 모두 합쳐주면 된다.

      그걸 어떻게 알아낼까..?? 이 부분 때문에 MAP[][]을 int형 vector로 선언해준 것이다.

      우리는 지금 (x, y)에 있는 군집들의 Index번호를 MAP[][]에 저장해주었다.

      즉, 예를들어서 MAP[x][y]의 size가 2이고 그 안에 데이터들을 보니 { 1, 2 }가 있다고 가정해보자.

      그렇다면 군집을 관리하는 벡터의 1번 인덱스와 2번인덱스가 여기에 합쳐져있다는 의미이다.

      이를 통해서 우리는 군집들을 합쳐줄 수가있다.

      물론 이 과정에서 나머지 군집들은 모두 죽여줘야 한다는 것도 주의하자.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int Num;
    int Dir;
    bool State;
}Bug;
 
int Answer;
int N, M, K;
vector<int> MAP[MAX][MAX];
vector<Bug> V;
 
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 };
 
void Initialize()
{
    Answer = 0;
    V.clear();
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            MAP[i][j].clear();
        }
    }
}
 
bool Standard(Bug A, Bug B)
{
    if (A.Num > B.Num) return true;
    return false;
}
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y, n, d;
        cin >> x >> y >> n >> d;
        Bug Temp;
        Temp.x = x; Temp.y = y;
        Temp.Num = n; Temp.Dir = d;
        Temp.State = true;
        V.push_back(Temp);
        
        MAP[x][y].push_back(i);
    }
}
 
void Move_Bug()
{
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
 
        MAP[V[i].x][V[i].y].clear();
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
 
        V[i].x = V[i].x + dx[V[i].Dir];
        V[i].y = V[i].y + dy[V[i].Dir];
        MAP[V[i].x][V[i].y].push_back(i);
    }
}
 
int Change_Direction(int Cur_D)
{
    if (Cur_D == 1) return 2;
    else if (Cur_D == 2) return 1;
    else if (Cur_D == 3) return 4;
    else if (Cur_D == 4) return 3;
}
 
void Kill_And_Sum_Bug()
{
    // Kill
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
 
        int x = V[i].x;
        int y = V[i].y;
        int d = V[i].Dir;
 
        if (x == 0 || y == 0 || x == N - 1 || y == N - 1)
        {
            V[i].Num = V[i].Num / 2;
            V[i].Dir = Change_Direction(d);
        }
 
        if (V[i].Num == 0)
        {
            V[i].State = false;
        }
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
 
        int x = V[i].x;
        int y = V[i].y;
 
        if (MAP[x][y].size() > 1)
        {
            int Sum = 0;
            int Biggest_Num = 0;
            int Select_Dir = 0;
            int Select_Idx = 0;
 
            for (int j = 0; j < MAP[x][y].size(); j++)
            {
                Sum = Sum + V[MAP[x][y][j]].Num;
                if (V[MAP[x][y][j]].Num > Biggest_Num)
                {
                    Biggest_Num = V[MAP[x][y][j]].Num;
                    Select_Dir = V[MAP[x][y][j]].Dir;
                    Select_Idx = MAP[x][y][j];
                }
                V[MAP[x][y][j]].State = false;
            }
 
            V[Select_Idx].Num = Sum;
            V[Select_Idx].Dir = Select_Dir;
            V[Select_Idx].State = true;
            MAP[x][y].clear();
            MAP[x][y].push_back(Select_Idx);
        }
    }
}
 
int Calculate()
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
        Sum = Sum + V[i].Num;
    }
    return Sum;
}
 
void Print()
{
    cout << "####################################" << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << MAP[i][j].size() << " ";
        }
        cout << endl;
    }
    cout << "####################################" << endl;
}
 
void Solution()
{
    for (int i = 0; i < M; i++)
    {
        Move_Bug();
        Kill_And_Sum_Bug();
    }
 
    Answer = Calculate();
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}