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

문제 링크

21611번: 마법사 상어와 블리자드 (acmicpc.net)

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

마법사 상어 시리즈 中 블리자드 편.

여태 풀었던 마법사 상어 문제중에 제일 까다로웠던 문제인 것 같다.

풀이

 

마법사 상어는 "블라자드"라는 새로운 마법을 배웠다. 그리고 이것을 N x N 격자판에서 연습중이다.

격자판의 크기는 항상 홀수이며 상어는 처음에 ((N+1)/2, (N+1)/2)에 있다. 즉 격자판의 한가운데에 있다는 의미이다.

 

격자에서 실선은 벽을 의미하고 점선 사이는 지나다닐 수 있다.

크기가 5인 (N = 5) 격자판을 예시로 보면 다음과 같이 격자판의 번호가 정해진다. 상어의 좌측을 시작으로 빙글빙글 돌아가면서 번호가 선정된다.

번호 배치가 이렇게 돼있어서 구현이 복잡했던 것 같다.

 

임의의 격자 칸을 선택했을 때, 다음 번호 칸이 어디인지를 바로 찾기가 쉽지 않다. 그래서 나는 처음에 N을 입력받은 후에 격자 칸을 정해진 순서대로 돌면서 Next라는 2차원 pair<int,int> 배열에 다음칸의 인덱스를 저장해두었다.

이렇게 하면 임의의 칸 (r,c) 에 대해서 다음 칸의 인덱스가 어디인지 바로 알 수 있다.

그리고 빈칸이 생기면 번호가 작은 칸으로 굴러가기 때문에 임의의 칸에 대해 이전 번호 칸이 어디인지도 알아야했다.

그래서 Before라는 2차원 pair<int,int> 배열도 선언해서 이전칸의 인덱스도 저장했다.

 

상어의 명령 이후의 구슬의 진행을 보면

블리자드 -> 구슬 재배열 -> 폭발 -> 재배열 -> 변화 순으로 발생하고, 폭발 과정은 폭발할 구슬이 없을 때까지 계속해서 발생한다.

위의 과정을 구현하기 위해서 어떤 정보들이 필요할까??

1. 현재 격자판의 상황

각 칸마다 현재 구슬이 들어있는지, 비어있는지 그리고 들어있다면 어떤 구슬이 들어있는 지를 항상 파악하고 있어야한다. 그리고 과정이 진행됨에 따라 격자판을 수정해주어야 한다.

A[50][50] 의 정수 배열을 만들어서 격자판의 상황을 저장했다.

2. 앞서 말했던 각 칸들의 다음칸과 이전칸을 알려주는 Next, Before 배열

3. 방향 배열

pair<int, int> Dir[] = { {0,0}, {-1,0}, {1,0}, {0,-1}, {0,1} };

방향은 1번~4번 4가지가 있으므로 0번 인덱스에는 편의를 위해 임의의 값을 넣어두었다.

필요한 정보들은 이정도가 될 것 같다.

 

• Next, Before 배열 값 대입

문제에서 주어진 격자판의 번호를 잘 들여다보자.

상어의 왼쪽 대각선인 2번부터 오른쪽으로 출발해서 2,2,3,3,4,4,5,5,6,6,.. 칸을 이동할 때마다 방향이 전환된다는 규칙이 있다. 이 규칙을 이용해서 Next배열과 Before 배열에 값을 지정해준다.

• 블리자드 마법

블리자드는 구현이 쉽다. d 방향으로 상어에서 s만큼 떨어진 칸까지 일자로 구슬을 파괴시키면 된다.

파괴된 구슬은 A배열에서 값을 0으로 변경시켜주면 된다.

• 재배열

번호가 작은 칸부터 큰 칸으로 이동하면서 해당 칸에 구슬이 있다면 그 구슬을 빈칸이 없을 때 까지 땡겨주면 된다.

그리고 원래 구슬이 있던 칸은 빈 칸이 된다.

• 폭발

1번 칸부터 마지막 칸까지 돌면서 번호가 같은 구슬들이 붙어있으면 모두 그룹으로 묶어준다. 그리고 그룹의 크기가 4이상이라면 해당 그룹의 구슬들을 폭발시킨다.

이때 (파괴된 구슬의 번호 * 구슬의 수) 의 총합이 우리가 출력해야할 정답이다.

폭발 -> 재배열 과정을 폭발할 구슬이 없을 때까지 반복한다.

• 변화

변화 과정 역시 1번 칸부터 마지막 칸까지 돌면서 번호가 같은 구슬들을 그룹으로 묶고, 그룹에 들어있는 구슬의 번호와 구슬의 수를 임의의 벡터에 저장해둔다. 이때 그룹의 크기는 상관없다.

모든 구슬들을 그룹으로 묶은 후, 임의의 벡터에 들어있는 정보를 이용해서 격자 칸의 구슬들을 변화시켜준다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 50 + 5;
int N, M;
pair<int, int> Dir[] = { {0,0}, {-1,0}, {1,0}, {0,-1}, {0,1} };
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int A[MAX_N][MAX_N];
pair<int, int> Shark;
pair<int, int> Next[MAX_N][MAX_N];
pair<int, int> Before[MAX_N][MAX_N];
int Score;
 
void Blizzard(int, int);
void Init();
void Arrange();
bool Explode();
void Change();
 
void Print_A() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            cout << A[i][j] << " ";
        cout << "\n";
    }
    cout << "\n";
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    Init();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < M; i++) {
        int d, s;
        cin >> d >> s;
        Blizzard(d, s);
        Arrange();
        while(Explode()) Arrange();
        Change();
    }
    cout << Score << "\n";
    return 0;
}
 
void Init() {
    Shark = { (1 + N) / 2, (1 + N) / 2 };
    pair<int, int> now = { Shark.first + 1, Shark.second - 1 };
    Next[Shark.first][Shark.second - 1] = now;
    Before[Shark.first][Shark.second - 1] = {-1,-1};
    Before[now.first][now.second] = { Shark.first, Shark.second - 1 };
    int direct = 1;
    for (int i = 2; i <= N; i++) {
        for (int k = 1; k <= 2; k++) {
            for (int j = 1; j <= i; j++) {
                pair<int, int> next = { now.first + dy[direct], now.second + dx[direct] };
                Next[now.first][now.second] = next;
                Before[next.first][next.second] = now;
                now = next;
                if (now.first == 1 && now.second == 1)
                    break;
            }
            if (now.first == 1 && now.second == 1)
                break;
            direct++;
            direct %= 4;
        }
        if (now.first == 1 && now.second == 1)
            break;
    }
    Next[1][1] = { -1,-1 };
}
 
void Blizzard(int d, int s) {
    for (int i = 1; i <= min((int)(N/2),s); i++) {
        pair<int, int> next = { Shark.first + Dir[d].first * i, Shark.second + Dir[d].second * i };
        A[next.first][next.second] = 0;
    }
}
 
void Arrange() {
    pair<int, int> now = { Shark.first + 1, Shark.second - 1 };
    while(true){
        if (now.first == -1 && now.second == -1)
            break;
        if (A[now.first][now.second] == 0) {
            now = Next[now.first][now.second];
            continue;
        }
        pair<int, int> to = now;
        while (true) {
            pair<int, int> before = Before[to.first][to.second];
            if (before.first == -1 && before.second == -1)
                break;
 
            if (A[before.first][before.second] == 0)
                to = before;
            else break;
        }
        if (to.first == now.first && to.second == now.second) {
            now = Next[now.first][now.second];
            continue;
        }
        A[to.first][to.second] = A[now.first][now.second];
        A[now.first][now.second] = 0;
    }
}
 
bool Explode() {
    pair<int,int> now = { Shark.first, Shark.second - 1 };
    vector<pair<int, int>> group;
    bool chk = false;
    for (int i = 1; i <= N * N - 1; i++) {
        if (A[now.first][now.second] == 0)
            break;
        pair<int, int> next = Next[now.first][now.second];
        if (A[now.first][now.second] == A[next.first][next.second]) {
            group.push_back(now);
            now = next;
            continue;
        }
        else {
            group.push_back(now);
            if (group.size() >= 4) {
                Score += A[now.first][now.second] * group.size();
                for (int j = 0; j < group.size(); j++) {
                    A[group[j].first][group[j].second] = 0;
                }
                chk = true;
            }
            now = next;
            group.clear();
        }
    }
    return chk;
}
 
void Change() {
    vector<pair<int, int>> Group;
    pair<int, int> now = { Shark.first, Shark.second - 1 };
    int cnt = 1;
    for (int i = 1; i <= N * N - 1; i++) {
        if (A[now.first][now.second] == 0)
            break;
        pair<int, int> next = Next[now.first][now.second];
        if (A[now.first][now.second] == A[next.first][next.second])
            cnt++;
        else{
            Group.push_back({ cnt,A[now.first][now.second] });
            cnt = 1;
        }
        now = next;
    }
    memset(A, 0, sizeof(A));
 
    now = { Shark.first, Shark.second - 1 };
    for (int i = 0; i < Group.size(); i++) {
        A[now.first][now.second] = Group[i].first;
        pair<int, int> next = Next[now.first][now.second];
        if (next.first == -1)
            break;
        A[next.first][next.second] = Group[i].second;
        now = Next[next.first][next.second];
        if (now.first == -1)
            break;
    }
}

코드의 길이가 꽤 길어졌다

코딩 테스트에 이 정도 구현문제가 나오면 시간이 오래걸려도 풀어야할까 넘겨야할까,,