[삼성기출] 백준 - C++ 마법사 상어와 블리자드

구현과 시뮬레이션 문제이다. 2021 상반기 문제 중 상대적으로 난이도가 높은 문제였다고 한다.

 

풀이

1. 마법

• dx[], dy[], DIR[] 을 이용하여 좌표로 접근하기
• 삭제된 구슬 자리는 빈칸(EMPTY = 0)으로 채워주기

2. 폭파

• map을 linearMap에 저장하기 (= Grid to Linear)
• vector<int> mList 를 선언해서, 폭파되지 않은 linearMap[idx] 는 mList 에 push_back()하기. 폭파됐을 경우에 flag = true
• index1, index2를 이용해서 동일한 번호의 구슬 개수를 찾는다. index2는 while()을 이용하여 index2++ 된다.
• 삭제된 개수는 index2 - index1, 삭제된 구슬번호는 linearMap[index1] 이므로, answer을 계산할 수 있다.

3. 변화

• vector<int> mList 를 선언해서, 구슬개수와 구슬번호를 계산하여 push_back() 한다.
• 이때, mList 의 크기는 N*N이 되어야 하기 때문에, 이를 위한 if문과 for문을 추가한다.
• linearMap에 mList를 대입한다.

4. setMap() //map 재정비

• M번의 블리자드를 위하여 map을 재정비한다.

---

1. Solution 코드

 

#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()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> 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() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            map[i][j] = 0;
    }
    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++) {
        cin >> d >> s;
        blizzard(d - 1, s);
        explodeMarble();
        changeMarble();
        setMap();
    }
    cout << ans << '\n';
}

채점 현황

 

2. 알아야 할 개념

1) map의 크기 N*N 에서 N이 홀수일 경우

 

2) 좌표 dx[4], dy[4]와 방향 DIR[4]

 

3) 변수명/함수명 팁

 

4) index를 채울건데, 반복이 보인다?

 

5) struct 로 좌표 표현하기