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

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

Approach

2021년 상반기 2번 문제로 구현 + 시뮬레이션 유형입니다.

개인적으로는 오전/오후 문제 4개 중에서 상대적으로 난이도가 높은 문제였던것 같습니다.

정해진 T/O나 응시자 평균을 비교해봐야 겠지만 1, 2번 문제를 모두 푸는것이 쉽지 않을 것 같습니다. 👀

 

문제를 복원/각색하면서 이해하기 어려운건지, 아니면 해석능력이 부족한건지...

다른 문제와 달리 내용 이해하기 위해서 2~3번 그림을 비교해가며 읽어야 했습니다. 😂

 

① d 방향으로 거리가 s 이하인 모든 칸의 구슬 파괴

    파괴된 칸은 빈 칸이 된다. (블리자드 마법)

② 구슬이 파괴된 후에는 빈 칸이 생겨 다음 인덱스의 구슬이 앞으로 당겨진다.

    다음 인덱스는 아래 그림에서 보이는 형태이다.

③ 같은 숫자로 4개 이상 연속되는 구슬들을 폭파시켜 없앤다.

    과정 ②, ③을 폭파되는 구슬이 없어질 때까지 반복

④  더 이상 폭발할 구슬이 없으면 구슬이 변화한다.

- {1, 1} 은 1번 구슬이 2개 있다. → {2, 1}

- {2} 은 2번 구슬이 1개 있다. → {1, 1}

- {3} 은 3번 구슬이 1개 있다. → {1, 3}

- 만약 {3, 3, 3}이 있다면 3번 구슬이 3개 있는 것이므로 {3, 3} 이 된다.

- 주어진 구슬의 칸 전체 개수보다 구슬이 많아질 수 없다.

▶ 과정 ① ~ ④ 까지를 M번 실행한 후,

    1 × (폭발한 1번 구슬의 개수) + 2 × (폭발한 2번 구슬의 개수) + 3 × (폭발한 3번 구슬의 개수) 계산

 

상어(중앙)를 기준으로 구슬을 순서대로 어떻게 배치(구현)할 지 중요하다.

구현하기 나름이겠지만 상어를 시작으로 {← , ↓ , → , ↑} 순으로

{1 - 1 - 2 - 2- 3 - 3 - 4 - 4 - 5 - 5 - 6 - 6 - 6 } 길이를 가지는데,

방향이 2번 변경될 때, 1칸씩 증가한다.

 

① 주어진 구슬 개수만큼 진행

② 2번 훑고 그 길이(len)가 ④에서 증가하다.

③ 주어진 길이(len) 만큼 DIR[dir] 방향만큼 한 칸씩 이동하며 구슬 확인 

 

이와 같은 특징을 이용해서 <정방행렬 90° 회전 (python)>을 구현해 본 적 있다.

여기서도 달팽이 등 같은 모양으로 이루어진 배치를 vector에 일렬로 배치하였다.

비슷한 기출유형으로는 <[BOJ] 17144 미세먼지 안녕> 에서 볼 수 있다.

[BOJ] 백준 17144 미세먼지 안녕

---

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

enum {
    EMPTY = 0,
};
const int MAX_N = 50;
const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = {  0, 0,-1, 1 };
const int DIR[4] = { 2, 1, 3, 0 }; // 좌 하 우 상
struct Node
{
    int x, y;
};
int N, M, totalCnt, ans, d, s, dir, len;
int map[MAX_N][MAX_N];
vector<int> marbleList;

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j]) totalCnt++;
        }
    }
}

void blizzard(int d, int s) {
    // d 방향으로 s 구간 구슬 파괴
    for (int i = 1; i <= s; i++) {
        int nextX = N / 2 + i * dx[d];
        int nextY = N / 2 + i * dy[d];
        // 원래 비워져 있는 경우
        if (map[nextX][nextY] == EMPTY)
            continue;
        map[nextX][nextY] = EMPTY;
        totalCnt--;
    }
}

void getMarble() {
    marbleList.clear();
    dir = 0, len = 1;
    Node cur = { N / 2, N / 2 };

    int idx = 0;
    while (idx != totalCnt) {
        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < len; i++) {
                cur.x += dx[DIR[dir]];
                cur.y += dy[DIR[dir]];

                // 빈 칸이 아닌 경우
                if (map[cur.x][cur.y]) {
                    marbleList.push_back(map[cur.x][cur.y]);
                    idx++;
                }

                // 모든 구슬을 저장한 경우
                if (idx == totalCnt)
                    return;
            }
            dir = (dir + 1) % 4;
        }
        len++;
    }
}

void explodeMarble() {
    // 현재 map[][] 에 존재하는 구슬 목록을 일렬로(vector) 들고온다.
    getMarble();

    bool flag = true;
    while (flag) {
        vector<int> mList;
        flag = false;
        for (int s = 0; s < marbleList.size(); s++) {
            int e = s;
            // 남은 구슬 중에서 같은 번호인지 확인
            while (e < marbleList.size() && marbleList[e] == marbleList[s])
                e++;

            if (e - s >= 4) // 같은 숫자로 연속된 구슬이 4개 이상인 경우
            {
                ans += marbleList[s] * (e - s);
                flag = true; // 계속해서 폭파 여부 조사를 위한 처리
            }
            else
            {
                // mList에 임시 보관
                for (int j = s; j < e; j++) {
                    mList.push_back(marbleList[j]);
                }    
            }
            // 탐색 지점(s) 재조정 
            s = e - 1;
        }
        // 남겨진 구슬들을 새로운 marbleList로 설정
        marbleList = mList;
    }
}

void changeMarble() {
    vector<int> mList;
    for (int s = 0; s < marbleList.size(); s++) {
        // 전체 N * N 칸으로 부족하게 되는 경우
        if (mList.size() >= N * N)
            break;

        int e = s;
        // 남은 구슬 중에서 같은 번호인지 확인
        while (e < marbleList.size() && marbleList[e] == marbleList[s])
            e++;

        mList.push_back(e - s); // 그룹에 속한 구슬 개수
        mList.push_back(marbleList[s]); // 해당 그룹의 구슬 번호

        // 탐색 시작 지점 재조정
        s = e - 1;
    }

    // 구슬개수가 범위를 초과한 경우, 개수 조절
    for (int i = mList.size(); i >= N * N; --i)
    {
        mList.pop_back();
    }
        
    marbleList = mList;
    totalCnt = marbleList.size();
}

void setMap() {
    memset(map, 0, sizeof(map));
    dir = 0, len = 1;
    Node cur = { N / 2, N / 2 };
    int idx = 0;
    while (idx != marbleList.size()) {
        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < len; i++) {
                cur.x += dx[DIR[dir]];
                cur.y += dy[DIR[dir]];
                map[cur.x][cur.y] = marbleList[idx++];
                
                // 주어진 구슬을 모두 재배치한 경우
                if (idx == marbleList.size())
                    return;
            }
            dir = (dir + 1) % 4;
        }
        len++;
    }
}

int main() {
    input();
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &d, &s);
        blizzard(d-1, s);
        explodeMarble();
        changeMarble();
        setMap();
    }
    printf("%d\n", ans);
}