백준 21611번: 마법사 상어와 블리자드 (C++)

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

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

접근

단순 구현 문제였다.

주어진 N * N 배열에 주어진 값들을 그대로 탐색하거나 재배치 하면서 문제를 풀지 않고, N * N 배열에서 탐색 순서대로 번호를 매겼다. 그리고 해당 번호를 인덱스로 하는 배열을 만들고, 값을 저장하고 탐색하는 방식으로 좀더 쉽게 접근할 수 있었다.

문제에서 주어진 예시) N = 7, d = 2, s = 2

48	47	46	45	44	43	42
25	24	23	22	21	20	41
26	9	8	7	6	19	40
27	10	1	0	5	18	39
28	11	2	3	4	17	38
29	12	13	14	15	16	37
30	31	32	33	34	35	36

Coord[N * N] = { 0, 1, 2, 3, 2, 2, 2, 1, 2, 1, 1, 3, 3, 3, 1, 3, 3, 1, 1, 1, 3, 2 ..... }

위와 같이 N * N 배열에 번호를 매겨놓고, 아래의 Coord 배열과 같이 번호 순서대로 값을 저장해두고 시작한다. 문제에서 주어진대로 d = 2, s = 2로 블리자드 마법을 수행한다면 파괴되는 구슬의 번호는 3번과 14번이다. 이는 Coord 배열의 인덱스와 같으므로 Coord[3]과 Coord[14]를 -1로 바꿔서 파괴된 구슬을 표기해줄 수 있다.

Coord[N * N] = { 0, 1, 2, -1, 2, 2, 2, 1, 2, 1, 1, 3, 3, 3, -1, 3, 3, 1, 1, 1, 3, 2 ..... }

그리고 -1을 무시하고 연속해서 4개 이상의 같은 번호 구슬이 있는 경우를 확인해보면, 2번 구슬 연속 4개, 3번 구슬 연속 5개로 총 9개의 구슬이 파괴된다. 마찬가지로 이 위치들을 모두 -1로 바꿔서 무시해주고 이 과정을 반복한다.

Coord[N * N] = { 0, 1, -1, -1, -1, -1, -1, 1, 2, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 3, 2 ..... }

1번 구슬 연속 5개로 파괴되고, 더 이상 폭발할 수 있는 구슬이 없으므로 과정을 마무리 한다.

코드

#include<iostream>
#include<cstring>

using namespace std;

#define endl '\n'
#define MAX_N 50

int N, M;
int MAP[MAX_N][MAX_N];
int ans[4] = { 0, 0, 0, 0 };
int Coord[MAX_N * MAX_N], NextCoord[MAX_N * MAX_N * 2];

int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, -1, 1 };


// Coord 배열의 1부터 끝까지 탐색하여 폭발 조건에 부합하는 칸들을 -1로 저장하고, 폭발이 일어났으면 1, 일어나지 않았으면 0 리턴
int Bomb()
{
    int flag = 0;
    int start = 1;
    while (Coord[start] == -1) start++;
    if (Coord[start] == 0) return flag;
    int val_old = Coord[start];
    int val_cnt = 1;
    int val;
    for (int i = start + 1; i < N * N; i++)
    {
        val = Coord[i];
        if (val == -1) continue;
        // 이전 값과 현재 값이 같으면 카운트++
        if (val_old == val) val_cnt++;
        else if (val_old != val && 4 <= val_cnt)
        {
            // 이전 값과 현재 값이 같지 않으면서 카운트가 4 이상이라면 폭발 발생
            flag = 1;
            ans[val_old] += val_cnt;
            // 폭발이 일어난 칸들을 -1로 저장
            int j = 0;
            while (0 < val_cnt)
            {
                j++;
                if (Coord[i - j] == -1) continue;
                Coord[i - j] = -1;
                val_cnt--;
            }
            // 폭발 후 새로 카운트 시작
            val_old = val;
            val_cnt = 1;
        }
        else
        {
            // 이전 값과 현재 값이 같지 않고 카운트가 4 미만이라면 폭발 없이 새로 카운트 시작
            val_old = val;
            val_cnt = 1;
        }
        if (val_old == 0) break;
    }
    return flag;
}


// 블리자드 마법을 수행하고, 폭발 후 구슬이 변화하는 단계까지 수행
void Blizard(int d, int s)
{
    memset(NextCoord, 0, sizeof(NextCoord));
    int r = N / 2;
    int c = N / 2;
    // 상어 위치에서 방향과 속도를 고려하여 구슬 파괴
    while (0 < s)
    {
        r += dr[d];
        c += dc[d];
        int sn = MAP[r][c];
        Coord[sn] = -1;
        s--;
    }
    // 폭발이 일어나지 않을 때까지 폭발 함수 계속 호출
    int flag = 1;
    while (flag != 0) flag = Bomb();
    // 구슬 변화 과정 수행
    int start = 1;
    int j = 1;
    while (Coord[start] == -1) start++;
    if (Coord[start] != 0)
    {
        int val_old = Coord[start];
        int val_cnt = 1;
        int val;
        for (int i = start + 1; i < N * N; i++)
        {
            if (Coord[i] == -1) continue;
            val = Coord[i];
            if (val_old == val) val_cnt++;
            else
            {
                NextCoord[j++] = val_cnt;
                NextCoord[j++] = val_old;
                val_old = val;
                val_cnt = 1;
            }
            if (val_old == 0) break;
        }
    }
    for (int i = 0; i < N * N; i++)
    {
        Coord[i] = NextCoord[i];
    }
}


// MAP을 이동 순서에 따라 번호 매기고, 해당 위치의 구슬값을 Coord 배열의 번호 인덱스에 저장
void MakeStructure()
{
    int r = N / 2;
    int c = N / 2;
    int dr2[] = { 0, 1, 0, -1 };
    int dc2[] = { -1, 0, 1, 0 };
    int step = 1;
    int dir = 0;
    int num = 0;
    Coord[0] = 0;
    while (!(r == 0 && c == 0))
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < step; j++)
            {
                r += dr2[dir];
                c += dc2[dir];

                Coord[++num] = MAP[r][c];
                MAP[r][c] = num;
            }
            dir++;
            if (dir == 4) dir = 0;
        }
        step++;
        if (step == N)
        {
            for (int j = 0; j < step - 1; j++)
            {
                r += dr2[dir];
                c += dc2[dir];

                Coord[++num] = MAP[r][c];
                MAP[r][c] = num;
            }
        }
    }
}


int main(int argc, char** argv)
{
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    MakeStructure();
    int d, s;
    for (int i = 0; i < M; i++)
    {
        cin >> d >> s;
        Blizard(d, s);
    }
    cout << ans[1] + ans[2] * 2 + ans[3] * 3 << endl;

    return 0;
}

더 생각해 볼 것?

문제를 더 효율적으로 풀기 위해 무언가 시도할 땐, 해당 코드가 원래 문제의 목적과 같은 결과를 갖도록 하는지 먼저 확인하자..

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!