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

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

삼성 기출이라 들었는데, 역시 소문대로 Gold1 치고는 어렵다고 느낀 문제였다.

🔍 문제분석

문제를 크게 세 파트로 나눠보자.

1. 입력
2. 구현
3. 출력

1. 입력

입출력에 까다로운 조건은 없는 문제이다.

먼저 N,M 이 주어진다. N은 구슬이 있는 정사각 형태의 2차원배열의 길이, M은 블리자드 횟수이다.

그리고 초기 구슬 배열이 주어진다.
구슬은 1,2,3 세 종류 중에 하나고 구슬이 없는 빈 칸과 상어가 있는 가운데 칸은 0으로 주어진다.

마지막으로 M번 만큼 블리자드 정보가 d,s로 주어진다. d는 방향, s는 상어로부터의 거리이다. 이 때 주의할 것은 상하좌우 순으로 1,2,3,4의 방향성을 갖는다.

다만 까다로운 점은 구슬의 이동이 N*N 배열의 가장 중심에 있는 상어로부터 나선형으로 뻗어가는 순서를 갖고 일어난다는 점이다.

2. 구현

블리자드를 한 번 할 때마다 또 다시 세 가지 페이즈를 갖는다고 볼 수 있다.

1. 블리자드 정보로 구슬 파괴
2. 네 개 이상 연속된 구슬 폭발
3. 갯수, 종류로 연속된 구슬을 카운해 다시 구슬 재배치

언뜻 보면 함수 세 개로 순서대로 blizzard, explode, rearrange 를 구현해서 풀 수 있을 것 같다고 처음엔 생각했다.

3. 출력

모든 블리자드와 그로 인한 세 가지 페이즈가 끝났다면 폭발 페이즈에서 각 구슬 종류마다 폭발된 구슬 갯수를 카운트하고 횟수*구슬번호의 합을 출력한다.

---

😢 문제 접근

문제를 풀면서 고려했던 주요 핵심은 네 가지였다.

1. 2차원 배열의 구슬은 나선형 순서로 어떻게 다룰 것인가?
2. 블리자드 마법의 구현 방법
3. 연쇄적인 폭발의 구현 방법
4. 재정렬 구현 방법

나선형 순서?

가장 처음 생각한 것은 2차원 형태의 배열을 1차원으로 펴는 것이다. 이 피는 방법도 두 가지 방법이 있다.

(N/2, N/2) 부터 시작해서 dx,dy로 배열을 나선형으로 탐색하면서 1차원배열에 순서대로 넣으면 된다.

그러나 난 조금 다른 방식을 택했다. (y,x)가 주어지면 바로 나선형의 몇번째 위치인지 알 수 있다고 생각했다. 분명 규칙성이 있고, 수식적으로 바로 변환 가능하다고 생각했고, 이를 flat() 함수로 구현 성공했다.

간략히 설명하자면,
현재 칸과 중심 칸과의 관계가 중요하다. 이 관계란 둘 사이의 거리와 방향 관계를 뜻한다.

둘 사이의 거리란 상어 칸(중심칸)과 현재 칸의 직접적인 거리가 아니다.

그림으로 설명하겠다.

우선 상어부터 시작해서 2차원 배열의 나선형 요소들은 노란색 레이어로 나누었다. 레이어마다 하->우->상->좌 순서대로 번호가 증가하는 패턴이 반복되기 때문이다. 상어를 제외한다면 구슬들은 n = 2*i+1 ( i = 1, 2, ..., (N-1)/2 ) 인 레이어에 소속된다.
n = l 인 레이어의 경우 l^2 번째 구슬부터 (l+1)^2-1 번째 구슬까지를 갖는다고 생각하면된다.

각 레이어는 빨간색, 파란색, 보라색, 초록색으로 순서대로 나누어서 생각했다. 그림 우하단의 색깔별 영역을 참고하자.
빨간색은 y가 증가하는 영역,
파란색은 x가 증가하는 영역,
보라색은 y가 감소하는 영역,
초록색은 x가 감소하는 영역이다.

앞서 언급했던 방향성은 네 영역 중 어느 것에 현재 칸이 속하는지를 뜻하는 것이다.

또한 중심 칸과의 거리란 속하는 영역과 중심 칸과의 거리를 뜻하는 것이다.

그럼 빨간색 동그라미가 현재 칸이라고 생각해보자. 따라서 중심 칸과의 거리는 2이며, 방향은 Down 이다.

그렇다면 어느 영역인지 어떻게 알까?

현재 칸 (y,x)와 상어칸 (N/2, N/2)과의 관계를 생각해보자.

편의상 int r = N/2 라고 하자.
dist는 영역과 상어와의 거리이다.

빨간색 영역은 y가 r - dist보다 크면서 x == r - dist이다.
파란색 영역은 빨간색 영역이 아니면서 y == r + dist이다.
보라색 영역은 파란색 영역이 아니면서 x == r + dist이다.
초록색 영역은 보라색 영역이 아니면서 y == r - dist이다.

그럼 몇 번째일까?

이 정보를 알았다면, 파란색 Down 영역의 첫 요소와 현재 칸이 얼만큼 떨어져 있는지만 알면, 나선형 배열에서 현재 칸이 몇 번째 요소인지 변환할 수 있다.

네 가지 영역의 첫 요소는 무엇인가?
우선 left, down, right, up 영역을 순서대로 0,1,2,3으로 dir이라고 정한다.

나선형 idx = (2d - 1)^2 + 2 * dir * dist + (각 영역 첫 요소와의 차)

코드는 다음과 같다. ifL이 left인지 = 빨간색 영역인지를 뜻한다.

int flat(int y,int x){
    int r = N / 2;
    int dist = max(abs(y - r), abs(x - r));

    if (dist == 0)
        return 0;

    int ifL = (y > r - dist) && (x == r - dist);
    int ifD = !ifL && (y == r + dist);
    int ifR = !ifD && (x == r + dist);
    int ifU = !ifR && (y == r - dist);
    int dir = ifL + ifD * 2 + ifR * 3 + ifU * 4 - 1; // 좌하우상
    int idx = (2 * dist - 1) * (2 * dist - 1) + 2 * dir * dist;
    idx += ifL * (dist - r + y - 1) + ifD * (dist - r + x - 1) + ifR * (r + dist - y - 1) + ifU * (r + dist - x - 1);

    return idx;
}

블리자드 페이즈

만약 나처럼 2차원 -> 1차원으로 펴서 문제를 풀었다면 문제가 다시 발생한다.
블리자드는 2차원배열에서 처리하기 쉽기에 상하좌우&거리 정보를 1차원 배열에서 몇 번째인지 변환해줘야한다.

사실 수식적으론 간단하다.

d 만큼 떨어진 칸은
좌측 = 4d^2 - 3d
하측 = 4d^2 - d
우측 = 4d^2 + d
상측 = 4d^2 +3d

까다로운 점은 dir이 좌하우상 순으로 주어지지않고 상하좌우 순으로 1,2,3,4로 주어진다는 것이다.

이 부분은 비트 연산으로 구현했다.

void blizzard(int dir, int dist){
    int cef, sign, idx;
    cef = dir & 1 ? 3 : 1;
    sign = dir & 2 ? -1 : 1;

    while (dist>0){
        idx = 4 * dist * dist + sign * cef * dist;
        flatten[idx] = 0;
        dist--;
    }
}

폭발 페이즈

처음에는 나선형 배열은 순서대로 loop를 돌면서 상어와 가까운 순으로 스택에 pair<int,int>에 {구슬종류, 갯수}를 넣으면서 top과 새로 들어오는 나선형 배열의 구슬을 비교하면서 다를 경우 4개 이상인 top을 pop하면 효과적일 것이라고 생각했다. 그렇게 구현했고, 44퍼센트에서 WA를 받았다...

반례는 다음과 같다.

9 1
0 0 0 0 0 0 0 0 0
3 2 1 3 1 3 3 3 0
1 3 3 3 1 3 3 1 0
0 2 2 2 1 2 2 1 0
0 1 2 1 0 2 2 1 0
0 3 3 1 1 2 2 2 0
0 3 3 3 1 1 1 2 0
0 1 1 1 3 3 3 2 0
0 0 0 0 0 0 0 0 0
1 3

output : 97

잘 생각해보면 구슬은 스택구조로 "상어와 가까운 순으로 터트리고 새로 쌓고"를 반복하면 문제의 가정과 다른 결과가 나온다.
문제의 상황에서는 "4개이상 연속인 구슬이 한번에 폭발 -> 구슬 이동"이 반복되는 구조이다. 즉 2개의 페이즈가 반복되는 설정이기에, 스택구조로 푼다면 한번에 터졌어야할 구슬이 같이 터지지 못하는 반례가 생긴다.

예시

3 111 2222 11 2222 1 3

스택 구조로 폭발 시켰을 시 결과 흐름

3
3 111
3 111 2222
3 111 2222 11 <-- top과 다른게 들어옴
3 111 (폭발) 11
3 11111
3 11111 2222 <-- top과 다른게 들어옴
3 (펑) 2222
3 2222
3 2222 1 <-- top과 다른게 들어옴
3 (폭발) 1
3 1
3 1 3
종료

문제대로 폭발 시켰을 시 변화

3 111 2222 11 2222 1 3
3 111 (폭발) 11 (폭발) 1 3
3 111 11 1 3
3 (퍼버벙) 3
3 3

해결 방법은 밑에서 언급하겠다.

재정렬 페이즈

폭발 페이즈가 끝났다면, 폭발 단계에서 사용한 {구슬종류, 갯수} 스택이 남아있을 것이다. 이 스택을 거꾸로 뒤집고 뒤에서부터 읽으면서 1차원 배열에 "갯수, 종류" 순으로 쓰기만 한다면 간단하게 재정렬이 끝난다.

만약 블리자드를 2차원 배열에서 하는 방식으로 구현했다면, 재정렬이 끝난 후 1차원 배열을 2차원으로 변환하는 과정을 거쳐야겠지만, 1차원 배열만으로 블리자드, 폭발, 재정렬이 이루어지므로 처음 한번을 제외하고는 모두 1차원 배열만 필요하다.

재정렬이 끝나고 다음 번 폭발 페이즈에 스택이 남아있으면 영향을 주게 되기 때문에 스택을 비워주는 단계도 필요하다.

또한 없어진 구슬 자리들을 0으로 채워줘야 인덱스 에러를 피할 수 있다.

void rearrange(){
    int idx = 1;

    reverse(stack.begin(), stack.end());

    while(!stack.empty()){
        if (idx >= N * N){
            stack.clear();
            break;
        }

        flatten[idx++] = stack.back().second;
        flatten[idx++] = stack.back().first;
        stack.pop_back();
    }

    while(idx<N*N){
        flatten[idx++] = 0;
    }
}

---

💡 다시 올바른 접근으로

올바른 폭발 방식을 다시 생각하자.

폭발 단계를 세분화하면

1. 연속된 {구슬종류, 갯수}로 이뤄진 스택을 만든다.
2. 갯수가 4이상인 요소는 카운트하면서 지운다.
3. 구슬이 없어졌다면 없어진 구슬들 앞뒤로 같은 종류라면 이어준다.
4. 더 이상 변화가 없을 때까지 2,3 단계를 반복한다.

구슬 폭발은 vector의 erase를 사용했다.
더 이상 변화가 없는지 확인은 3번 단계에서 한 번이라도 이어주면 true를, 변화가 없으면 false 반환해 감지하도록 만들었다.

explode() 함수에서 1 ~ 3번 페이즈를 4번에 따라 구현했다.

void initStack(){
    for (int i = 0; i < N * N; i++){
        int next = flatten[i];
        if (next == 0)
            continue;
        
        if (stack.empty() || stack.back().first!=next){
            stack.push_back({next, 1});
            continue;
        } else if (stack.back().first == next){
            stack.back().second++;
        }
    }
}

void explodeStack(){
    vector<pii>::iterator it = stack.begin();
    while (!stack.empty() && it != stack.end()){
        pii elem = *it;
        if (elem.second < 4){
            it++;
            continue;
        }
        bombCnt[elem.first] += elem.second;
        it = stack.erase(it);
    }
}

bool updateStack(){
    vector<pii>::iterator it = stack.begin() + 1;
    bool isChanged = false;

    while(!stack.empty() && it != stack.end()){
        if ((*(it - 1)).first == (*it).first){
            (*(it - 1)).second += (*it).second;
            it = stack.erase(it);
            isChanged = true;
        }else{
            it++;
        }
    }
    return isChanged;
}

void explode(){
    bool isChanged = true;
    initStack();

    while (isChanged){
        explodeStack();
        isChanged = updateStack();
    }
}

---

✅ 정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef pair<int, int> pii;

int N, M;
int board[49][49];
vector<int> flatten(2401); // 2차원 배열 -> 1차원 벡터
vector<pii> stack; // <구슬번호, 갯수>
vector<int> arranged(2401); // 폭발 후 그룹핑 벡터
int bombCnt[4] = {0, 0, 0, 0}; // 0번째 더미 + 각 구슬의 폭발횟수 카운트
int dy[5] = {-1, 1, 0, 0};
int dx[5] = {0, 0, -1, 1}; // 상하좌우

void input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N;j++){
            cin >> board[i][j];
        }
    }
}

int flat(int y,int x){
    int r = N / 2;
    int dist = max(abs(y - r), abs(x - r));

    if (dist == 0)
        return 0;

    int ifL = (y > r - dist) && (x == r - dist);
    int ifD = !ifL && (y == r + dist);
    int ifR = !ifD && (x == r + dist);
    int ifU = !ifR && (y == r - dist);
    int dir = ifL + ifD * 2 + ifR * 3 + ifU * 4 - 1; // 좌하우상
    int idx = (2 * dist - 1) * (2 * dist - 1) + 2 * dir * dist;
    idx += ifL * (dist - r + y - 1) + ifD * (dist - r + x - 1) + ifR * (r + dist - y - 1) + ifU * (r + dist - x - 1);

    return idx;
}

void flat2D(){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N;j++){
            flatten[flat(i, j)] = board[i][j];
        }
    }
}

void blizzard(int dir, int dist){
    int cef, sign, idx;
    cef = dir & 1 ? 3 : 1;
    sign = dir & 2 ? -1 : 1;

    while (dist>0){
        idx = 4 * dist * dist + sign * cef * dist;
        flatten[idx] = 0;
        dist--;
    }
}

void initStack(){
    for (int i = 0; i < N * N; i++){
        int next = flatten[i];
        if (next == 0)
            continue;
        
        if (stack.empty() || stack.back().first!=next){
            stack.push_back({next, 1});
            continue;
        } else if (stack.back().first == next){
            stack.back().second++;
        }
    }
}

void explodeStack(){
    vector<pii>::iterator it = stack.begin();
    while (!stack.empty() && it != stack.end()){
        pii elem = *it;
        if (elem.second < 4){
            it++;
            continue;
        }
        bombCnt[elem.first] += elem.second;
        it = stack.erase(it);
    }
}

bool updateStack(){
    vector<pii>::iterator it = stack.begin() + 1;
    bool isChanged = false;

    while(!stack.empty() && it != stack.end()){
        if ((*(it - 1)).first == (*it).first){
            (*(it - 1)).second += (*it).second;
            it = stack.erase(it);
            isChanged = true;
        }else{
            it++;
        }
    }
    return isChanged;
}

void explode(){
    bool isChanged = true;
    initStack();

    while (isChanged){
        explodeStack();
        isChanged = updateStack();
    }
}

void rearrange(){
    int idx = 1;

    reverse(stack.begin(), stack.end());

    while(!stack.empty()){
        if (idx >= N * N){
            stack.clear();
            break;
        }

        flatten[idx++] = stack.back().second;
        flatten[idx++] = stack.back().first;
        stack.pop_back();
    }

    while(idx<N*N){
        flatten[idx++] = 0;
    }
}

void solution(){
    int dir, dist, ans = 0;
    input();
    flat2D();
    while (M--){
        cin >> dir >> dist;
        blizzard(dir, dist);
        explode();
        rearrange();
    }
    ans = bombCnt[1] + bombCnt[2] * 2 + bombCnt[3] * 3;
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    solution();
}

---

📒 마치며

구현 문제는 꼼수 부리지말고, 문제 그대로 구현하자...

vector erase는 지운 위치의 iterator를 반환한다. 기억하자