[BOJ] 21611 - 마법사 상어와 블리자드

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

21611번: 마법사 상어와 블리자드

난이도

단순구현 / 난이도 ⭐️⭐️⭐️ / 2.5시간

 

문제 풀이

단순 구현 문제이다. 구슬 이동을 어떻게 구현할 것인지가 가장 중요한 포인트이다.

나는 구슬 순서를 담은 일차원 벡터와, 일차원 벡터에 접근하기 위한 인덱스를 값으로 가지는 2차원 배열로 구현했다.

예를 들어 아래 조건일 경우 다음과 같은 자료형을 추가한 것이다.

구슬의 순서를 담은 일차원 벡터 : 0(상어), 1, 2, 3, 2, 2, 2, 1, 2

일차원 벡터에  접근하기 위한 인덱스 값을 가지는 2차원 배열 :

8 7 6

1 0 5

2 3 4

 

이 외, 구현 중 등호 (> >=) 같은 사소한 부분들만 조심해주면 될 것 같다고 생각하고 풀었다.

#include <iostream>
#include <vector>
#include <stdio.h>
#include <utility>
#include <stack>
using namespace std;

int arr[51][51] = {0};
int n, m;

vector<int> v;
int arr2[51][51] = {0};

int removed_circle[] = {0, 0, 0, 0}; // 폭발한 1번구슬, 2번구슬, 3번구슬 개수

int pre()
{
    int rotatex[] = {0, 1, 0, -1};
    int rotatey[] = {-1, 0, 1, 0};
    int arr2_cnt = 0;
    int x, y;

    x = (n + 1) / 2;
    y = (n + 1) / 2;
    v.push_back(arr[x][y]);
    arr2[x][y] = arr2_cnt++;

    int dir_cnt = 1;
    int dir_index = 0;
    while (true)
    {
        for (int z = 0; z < dir_cnt; z++)
        {
            x = x + rotatex[dir_index];
            y = y + rotatey[dir_index];
            if (x < 1 || y < 1)
            {
                return 0;
            }
            arr2[x][y] = arr2_cnt++;
            if (arr[x][y] != 0)
                v.push_back(arr[x][y]);
        }

        dir_index++;
        if (dir_index == 4)
            dir_index = 0;

        for (int z = 0; z < dir_cnt; z++)
        {
            x = x + rotatex[dir_index];
            y = y + rotatey[dir_index];
            if (x < 1 || y < 1)
            {
                return 0;
            }
            arr2[x][y] = arr2_cnt++;
            if (arr[x][y] != 0)
                v.push_back(arr[x][y]);
        }

        dir_index++;
        if (dir_index == 4)
            dir_index = 0;

        dir_cnt++;
    }
}

vector<int> explosion()
{

    vector<int> v2;
    v2.push_back(0);

    // check point 2)
    if (v.size() == 1)
        return v2;

    int cur_circle_number = v[1];
    int cur_circle_cnt = 1;
    for (int i = 2; i < v.size(); i++)
    {
        if (v[i] == cur_circle_number)
        {
            cur_circle_cnt++;
        }
        else
        {
            if (cur_circle_cnt < 4)
            {
                for (int j = 0; j < cur_circle_cnt; j++)
                {
                    v2.push_back(cur_circle_number);
                }
            }
            else
            {
                removed_circle[cur_circle_number] += cur_circle_cnt;
            }
            cur_circle_number = v[i];
            cur_circle_cnt = 1;
        }
    }

    if (cur_circle_cnt < 4)
    {
        for (int j = 0; j < cur_circle_cnt; j++)
        {
            v2.push_back(cur_circle_number);
        }
    }
    else
    {
        removed_circle[cur_circle_number] += cur_circle_cnt;
    }

    return v2;
}

int main()
{
    int dirx[] = {0, -1, 1, 0, 0}; // 위 아래 왼쪽 오른쪽 , 1 2 3 4
    int diry[] = {0, 0, 0, -1, 1};

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d ", &arr[i][j]);
        }
    }

    pre();

    int d, s;
    int centerx = (n + 1) / 2;
    int centery = (n + 1) / 2;
    int newx, newy;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &d, &s);

        // 구슬파괴 및 이동
        newx = centerx;
        newy = centery;
        stack<int> v_index;
        for (int j = 0; j < s; j++)
        {
            newx += dirx[d];
            newy += diry[d];
            v_index.push(arr2[newx][newy]);
        }

        while (!v_index.empty())
        {
            if (v.size() > v_index.top())
            {
                v.erase(v.begin() + v_index.top());
            }
            v_index.pop();
        }

        // 4개 이상 연속하는 구슬 제거
        while (1)
        {
            vector<int> new_v = explosion();
            if (new_v.size() == v.size())
            {
                break;
            }
            v.clear();
            v.assign(new_v.begin(), new_v.end());
        }

        // grouping  갯수 / 구슬 번호 순서로
        vector<int> v2;
        v2.push_back(0);

        if (v.size() > 1) // check point 2)
        {
            int cur_circle_number = v[1];
            int cur_circle_cnt = 1;
            for (int j = 2; j < v.size(); j++)
            {
                if (v[j] == cur_circle_number)
                {
                    cur_circle_cnt++;
                }
                else
                {
                    v2.push_back(cur_circle_cnt);
                    v2.push_back(cur_circle_number);
                    cur_circle_number = v[j];
                    cur_circle_cnt = 1;
                }
            }
            v2.push_back(cur_circle_cnt);
            v2.push_back(cur_circle_number);

            if (v2.size() > n * n)
            {
                v2.erase(v2.begin() + (n * n), v2.end());
            }
        }

        v.clear();
        v.assign(v2.begin(), v2.end());

    } // for end m

    //result
    printf("%d", removed_circle[1] + removed_circle[2] * 2 + removed_circle[3] * 3);
}

 

주의 조건

 

처음에 check point 2) 부분을 추가하지  않았는데, 63%까지 채점이 되고 "틀렸습니다." 가 결과로 나왔다.

 

코드를 처음부터 읽으면서 a > b , a >= b, a > b + 1 과  같은 부분과, 없는 인덱스에 접근하는 경우를 집중적으로 살펴보았다.

check point 2를 추가하면서 채점에 통과할 수  있었는데, 정확한 이유는 실험해보지 않아서 모르겠다.

아마 구슬 폭발이 일어나면서 모든 구슬이 사라지고 오직  상어만 남는 경우가 생기는데, 이때 없는 인덱스인 v[1]에 접근하려고 해서 틀렸습니다. 라는 결과가 나온 것 같다. 

하지만 index out of range와 같은 오류가 안나오고 틀렸습니다 라는 결과가 나왔는지는 잘 모르겠다.

 

"빠짐없이 다  구현했는데  왜 틀렸지..;;" 라는 생각보다
"분명 어떤  조건을 빼먹었거나 실수를 했구나" 라는 생각으로 접근하는게 중요하다.

 

풀면서 찾아봤던  문법, 주요 문법

벡터 복사

desVector.assign(sourceVector.begin(), sourceVector.end());

 

벡터에서 특정 인덱스 구간 삭제

v.erase(v.begin() + x, v.begin() + y); (?)

v.erase(v.begin() + x, v.end());

 

#include <stack>

push(), top(), pop()

 

#include <queue>

push(), front(), pop()

 

주어진 일차원 배열에서 4번 이상 연속되는 같은 문자 제거하기

1 2 2 2 2 3 4 5 5 6 6 => 1 3 4 5 5 6 6