마법사 상어와 블리자드

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

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

일단 마법사 상어와 토네이도에서 

나선형으로 도는 것은 풀어봤다.

 

모든 과정마다

나선형을 전부 다 돌면서

처리하는 것이 괜찮을까?

아니! 비효율적이다.

 

철저하게 경우를 생각하면서

케이스를 따져야한다.

 

1. 문제 시작에 '칸의 번호'라고 주어진다.

토네이도 구현을 하면서

"칸의 번호"와 "칸의 번호에 맞는 좌표"를 저장하자.

jwa wichi[55 * 55]

int n_map[55][55];

 

2. 블리자드

'터뜨린 다음 바로 밀기'가 아니라!

bool sakujyo[55 * 55];

터뜨리는 애를 체크하고 

나중에 당기자

 

3. 터진 다음 구슬 당기기

1부터 n * n - 1까지 순회

sakujyo[i]가 true면 cnt를 증가

false라면 cnt만큼 앞으로 당겨준다.

 

마지막 경우 두 가지

a) 구슬이 다 안차있는 경우 (map값이 0)

j = 1부터 cnt까지 map 값을 0으로

flag = false; break;

 

b) 구슬이 가득 찬 경우

i = n * n - 1, j = 1부터 cnt까지 

i-- 하면서 map 값을 0으로

 

4. 이어진 구슬 찾기

cur_marble

sequence_cnt = 1

start_num = 1;

 

num 2부터 n * n - 1까지 순회

next_marble = wichi[num]의 구슬

cur_marble과 같다면

sequence_cnt++;

다르다면

a) sequence_cnt >= 4라면

start_num부터 num - 1까지 

sakujyo에 true 표시해준다.

 

cur_marble = next_marble;

sequence_cnt = 1;

start_num = num;

 

마지막 체크!

마지막에서 sequence_cnt >= 4인지 체크하고

4보다 크다면 당겨줘야한다.

 

5. 맵 새로 만들기

change() 함수

3개가 연속되는 경우에는 어떻게 되는가?

 

1 2 3 4 : genzai

1 1 1 2

 

현재 genzai는 4

next_marble = 2

3 1 을 넣고

cnt_jari += 2 하니까

cnt_jari는 3

 

즉, 상관이 없다.

중요한 것은 cnt_jari!

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct jwa {
    int x, y;
};
 
jwa shark;
jwa wichi[55 * 55];
bool sakujyo[55 * 55];
 
int map[55][55];
int n_map[55][55];
 
vector<pair<int, int>> ice;
 
int n, m;
int marble[4];
 
// 상 하 좌 우
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0,0,-1, 1 };
 
// 좌 하 우 상으로 돈다
int change_dir(int dir) 
{
    if (dir == 0) return 2;
    if (dir == 1) return 3;
    if (dir == 2) return 1;
    if (dir == 3) return 0;
}
 
// 맵을 새로 만든다
// 토네이도와 동일하다
void make_map() 
{
    int x = (n + 1) / 2;
    int y = (n + 1) / 2;
    int move_cnt = 1;
    int num = 0;
    int dir = 2;
 
    shark = { x, y };
    n_map[x][y] = num;
    wichi[num++] = { x,y };
 
    while (true)
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < move_cnt; j++)
            {
                x += dx[dir];
                y += dy[dir];
                n_map[x][y] = num;
                wichi[num++] = { x,y };
            }
            dir = change_dir(dir);
        }
        move_cnt++;
 
        if (move_cnt == n)
        {
            for (int j = 0; j < move_cnt; j++)
            {
                x += dx[dir];
                y += dy[dir];
                n_map[x][y] = num;
                wichi[num++] = { x,y };
            }
            break;
        }
    }
}
 
void blizzard(int idx)
{
    memset(sakujyo, false, sizeof(sakujyo));
    int dir = ice[idx].first;
    int k = ice[idx].second;
 
    int x = shark.x;
    int y = shark.y;
 
    for (int i = 0; i < k; i++)
    {
        x += dx[dir];
        y += dy[dir];
        sakujyo[n_map[x][y]] = true;
    }
}
 
// 터진 다음 구슬 옮기기
void move_marble()
{
    bool flag = false;
    int cnt = 0;
 
    for (int i = 1; i < n * n; i++)
    {
        if (sakujyo[i] == true)
        {
            flag = true;
            cnt++;
        }
        else
        {
            // 구슬이 없는 경우, 즉 구슬 꼬리를 지나감
            if (map[wichi[i].x][wichi[i].y] == 0) {
                for (int j = 1; j <= cnt; j++)
                    map[wichi[i - j].x][wichi[i - j].y] = 0;
 
                // 이거 해주고 break 해야한다!
                flag = false;
                break;
            }
            // cnt만큼 앞으로 당겨준다.
            else
                map[wichi[i - cnt].x][wichi[i - cnt].y] = map[wichi[i].x][wichi[i].y];
        }
    }
 
    // 구슬이 가득 차있는 경우
    if (flag == true)
    {
        int i = (n * n) - 1;
        for (int j = 1; j <= cnt; j++, i--)
            map[wichi[i].x][wichi[i].y] = 0;
    }
}
 
bool destroy_sequence()
{
    memset(sakujyo, false, sizeof(sakujyo));
 
    bool flag = false;
    int cur_marble = map[wichi[1].x][wichi[1].y];
    int sequence_cnt = 1;
    int start_num = 1;
 
    int num;
    for (num = 2; num < n * n; num++)
    {
        int next_marble = map[wichi[num].x][wichi[num].y];
 
        // 마지막에 닿았다
        if (next_marble == 0)
            break;
 
        // 같다면 sequence_cnt++
        if (cur_marble == next_marble)
            sequence_cnt++;
        // 다르다면
        else
        {
            // sakujyo에 체크
            if (sequence_cnt >= 4)
            {
                flag = true;
                for (int i = start_num; i < num; i++)
                    sakujyo[i] = true;
                marble[cur_marble] += sequence_cnt;
            }
 
            cur_marble = next_marble;
            sequence_cnt = 1;
            start_num = num;
        }
    }
 
    // 마지막까지 갔을 때 sequence_cnt >= 4 일수도 있으므로
    if (sequence_cnt >= 4)
    {
        flag = true;
        for (int i = start_num; i < num; i++)
            sakujyo[i] = true;
        marble[cur_marble] += sequence_cnt;
    }
 
    return flag;
}
 
// 맵 새로 만들기
void change()
{
    // 바꿀 맵
    int tmp[55][55] = { 0, };
    
    int cur_marble = map[wichi[1].x][wichi[1].y];
    int cnt = 1;
    int cnt_jari = 1;
    bool flag = true;
 
    for (int genzai = 2; genzai < n * n; genzai++)
    {
        // 넣을 자리가 범위 넘어가버리면 그냥 버린다.
        if (cnt_jari >= n * n)
        {
            flag = false;
            break;
        }
 
        int next_marble = map[wichi[genzai].x][wichi[genzai].y];
        // 0이 나오면 더 이상 구슬이 없다는 말
        if (next_marble == 0)
            break;
 
        if (cur_marble == next_marble)
            cnt++;
        // 다르면 이제 chg
        else
        {
            tmp[wichi[cnt_jari].x][wichi[cnt_jari].y] = cnt;
            tmp[wichi[cnt_jari + 1].x][wichi[cnt_jari + 1].y] = cur_marble;
            cur_marble = next_marble;
            cnt = 1;
            cnt_jari += 2;
        }
    }
 
    // 마지막 처리
    // 0이 나와서 끝난 상태이거나
    // 마지막까지 같은 구슬이 나와서 cnt가 증가한 상태
    if (flag == true)
    {
        if (cnt_jari != 1)
        {
            tmp[wichi[cnt_jari].x][wichi[cnt_jari].y] = cnt;
            tmp[wichi[cnt_jari + 1].x][wichi[cnt_jari + 1].y] = cur_marble;
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            map[i][j] = tmp[i][j];
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        ice.push_back({ a - 1, b });
    }
 
    make_map();
    
    for (int i = 0; i < m; i++)
    {
        blizzard(i);
        move_marble();
 
        while (true)
        {
            if (destroy_sequence() == false)
                break;
            move_marble();
        }
        change();
    }
 
    int ans = marble[1] + (2 * marble[2]) + (3 * marble[3]);
    cout << ans << '\n';
}