백준 g1 21611 마법사 상어와 블리자드 c++

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

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

 

문제 설명

N*N의 보드가 주어지고, 나선형으로 길이 뚫려있다. 마법사 상어는 보드의 정중앙에 위치한다. { (N+1)/2, (N+1)/2 }

각 칸에는 1, 2, 3이 적혀있는 구슬이 하나씩 들어있다.

 

1) 마법사 상어는 M번 블리자드 마법을 si칸만큼, di 방향으로 쏜다.

블리자드 마법을 맞는 칸의 구슬은 없어진다.

 

1-1) 구슬이 비어있으면, 그 뒤의 구슬이 나선형 길을 따라 비어있는 칸 만큼 앞으로 모두 땡겨진다.

 

2) 나선형 길을 따라, 같은 숫자가 4개 이상 연속된 구슬은 모두 파괴된다.

2-1) 파괴된 칸만큼 뒤에 있는 구슬이 땡겨진다.

더이상 파괴되는 구슬이 없을 때까지 2번 과정을 반복한다.

 

3) 연속하는 구슬을 하나의 그룹으로 두고, 하나의 그룹은 <그룹 내 구슬의 개수, 그룹 내 구슬의 번호> 2개의 구슬로 바뀐다.

 

1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수) 를 출력하기

풀이

1. board의 나선형 길 -> coord라는 linear 구조로 변경

나선형은 ←, ↓, → , ↑ 순서로 1, 1, 2, 2, 3, 3, ... 칸씩 앞으로 간다. 이런 특성을 사용해서, 

N=3인 보드에 index가 1~8 저렇게 주어지면, coord 벡터에 = {(2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 2), (1, 1)}로 저장해둔다. 이렇게 하면 board <-> 실제 값이 들어있는 linear vector의 전환이 자유롭게 된다.

// board의 나선형 길 idx -> coord라는 이차원 벡터로 바꾸는 함수
vector<pair<int, int>> coord;

void getIndexVector() {
    int sx = (N + 1) / 2;
    int sy = (N + 1) / 2;
    int ind = 0;
    int dir = -1;
    int len = 0;
    while (ind <= N * N - 1) {
        dir = (dir + 1) % 4;
        len++;
        int nx, ny;
        for (int j = 0; j < len; j++) {
            nx = sx + dx[dir];
            ny = sy + dy[dir];

            ind++;
            coord.push_back({nx, ny});
            sx = nx;
            sy = ny;
            if (ind == N * N - 1) return;
        }

        dir = (dir + 1) % 4;
        for (int j = 0; j < len; j++) {
            nx = sx + dx[dir];
            ny = sy + dy[dir];

            ind++;
            coord.push_back({nx, ny});
            sx = nx;
            sy = ny;
            if (ind == N * N - 1) return;
        }
    }
}

 

 

2. 블리자드로 구슬 파괴

그냥 해당 board에 si, di 방향대로 구슬을 부수고 0으로 바꿔주면 된다.

이때 dir에 주의. 

( 나는 위 getIndexVector에서 나선형 순서대로 dir을 설정해줬고, 이는 di의 방향 번호랑 다르다)

void blizzard() {
    int sx = (N + 1) / 2;
    int sy = (N + 1) / 2;

    for (int i = 0; i < si; i++) {
        int nx = sx + dx[di];
        int ny = sy + dy[di];

        sx = nx;
        sy = ny;
        board[nx][ny] = 0;
    }
}

 

3. 될 때까지 4개 이상인 구슬 파괴하기

while (1) {
    if (destroyMarble() == false) break;
}

 

3-1. 먼저 blizzard로 삭제된 구슬을 고려해서, board에서 나선형으로 적혀있는 구슬들을 tmp라는 선형 데이터 vector에 담아준다.

이때 destroyMarble함수가 많이 호출되는 만큼 vector<int>도 계속 생길 거 같애서 메모리가 넘치면 어떡하지? 걱정했지만

함수가 끝나면 지역변수는 어차피 사라진다(정확하게는 값은 남아있지만 언제든지 덮어쓸 수 있는 상태가 된다)

 

그리고 어차피 메모리는 넘칠만큼 주어지니까 마음껏 쓰고 대신 복잡하게 말고 직관적으로 코드를 짜자

bool destroyMarble() {
    vector<int> tmp;

    for (pair<int, int> cur : coord) {
        int x = cur.first;
        int y = cur.second;
        if (board[x][y] == 0) continue;

        tmp.push_back(board[x][y]);
    }

 

3-2. cnt, prev란 변수를 사용해서 4개 연속인 애들을 0으로 파괴한다.

여기서 주의할 점은 prev != cur 일 때만 tmp에 영향을 주므로, 꼭 마지막에 남는 구슬을 고려해줘야 한다 !!

나는 마지막에 남는 구슬을 고려하는 덴 성공했지만, 마지막에 남는 구슬의 점수 구하는 거를 tmp를 0으로 바꾸는 statement와 순서를 바꿔서 94%에서 틀렸습니다가 떴다. 마지막까지 실수에 주의해야 한다 ..

    // 4개 연속인 애들 0으로 파괴
    bool res = false;
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < tmp.size(); i++) {
        int cur = tmp[i];
        if (prev != cur) {
            if (cnt >= 4) {
                for (int j = 1; j <= cnt; j++) {
                    tmp[i - j] = 0;
                }
                ans[prev] += cnt;
                cnt = 1;
                prev = cur;
                res = true;
            } else {
                cnt = 1;
                prev = cur;
            }
        } else {
            cnt++;
        }
    }
    // 마지막꺼
    if (cnt >= 4) {
        ans[tmp.back()] += cnt;
        for (int j = 1; j <= cnt; j++) {
            tmp[tmp.size() - j] = 0;
        }
    }

 

3-3. 파괴된 구슬은 냅두고, 아닌 애들을 coord 배열을 사용해서 다시 board에 옮겨담는다.

// 다시 board에 push
    int idx = 0;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            board[i][j] = 0;
    for (int v : tmp) {
        if (v == 0) continue;
        int x = coord[idx].first;
        int y = coord[idx].second;
        board[x][y] = v;
        idx++;
    }
    // printBoard();
    return res;

 

4. 구슬 그룹 -> 구슬 A, 구슬 B로 변환하기

3번 과정과 비슷하게 하면 된다. 대신 이때는 구슬의 길이가 board를 넘을 수 있으므로, 그때 cut해줘야 한다.

void changeMarble() {
    // 1. board -> vector
    vector<int> tmp;

    for (pair<int, int> cur : coord) {
        int x = cur.first;
        int y = cur.second;
        if (board[x][y] == 0) continue;

        tmp.push_back(board[x][y]);
    }

    // 2. group -> marble A and B
    vector<int> changed;
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < tmp.size(); i++) {
        int cur = tmp[i];
        if (prev != cur) {
            changed.push_back(cnt);
            changed.push_back(prev);
            cnt = 1;
            prev = cur;
        } else {
            cnt++;
        }
    }
    // 마지막 꺼
    changed.push_back(cnt);
    changed.push_back(prev);

    // 3. vector -> board
    int idx = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            board[i][j] = 0;
    for (int v : changed) {
        if (idx > N * N - 1) break;
        if (v == 0) continue;
        int x = coord[idx].first;
        int y = coord[idx].second;
        board[x][y] = v;
        idx++;
    }
}

 

전체 코드

/*boj g1 21611 마법사 상어와 블리자드*/
#include <iostream>
#include <vector>
#define MAXN 52
using namespace std;

int N, M, di, si;
int board[MAXN][MAXN];
vector<pair<int, int>> coord;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int ans[4]; // -, 1번 구슬 개수, 2번 구슬 개수, 3번 구슬 개수

void printBoard() {
    cout << "=============\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}

void printVector(vector<int> &vec) {
    for (int a : vec) {
        cout << a << " ";
    }
    cout << "\n";
}
void input() {
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> board[i][j];
        }
    }
}

void getIndexVector() {
    int sx = (N + 1) / 2;
    int sy = (N + 1) / 2;
    int ind = 0;
    int dir = -1;
    int len = 0;
    while (ind <= N * N - 1) {
        dir = (dir + 1) % 4;
        len++;
        int nx, ny;
        for (int j = 0; j < len; j++) {
            nx = sx + dx[dir];
            ny = sy + dy[dir];

            ind++;
            coord.push_back({nx, ny});
            sx = nx;
            sy = ny;
            if (ind == N * N - 1) return;
        }

        dir = (dir + 1) % 4;
        for (int j = 0; j < len; j++) {
            nx = sx + dx[dir];
            ny = sy + dy[dir];

            ind++;
            coord.push_back({nx, ny});
            sx = nx;
            sy = ny;
            if (ind == N * N - 1) return;
        }
    }
}

void blizzard() {
    int sx = (N + 1) / 2;
    int sy = (N + 1) / 2;

    for (int i = 0; i < si; i++) {
        int nx = sx + dx[di];
        int ny = sy + dy[di];

        sx = nx;
        sy = ny;
        board[nx][ny] = 0;
    }
}

int convertDir(int dir) {
    if (dir == 3)
        return 0;
    else if (dir == 2)
        return 1;
    else if (dir == 4)
        return 2;
    else if (dir == 1)
        return 3;
}

bool destroyMarble() {
    vector<int> tmp;

    for (pair<int, int> cur : coord) {
        int x = cur.first;
        int y = cur.second;
        if (board[x][y] == 0) continue;

        tmp.push_back(board[x][y]);
    }

    // 4개 연속인 애들 0으로 파괴
    bool res = false;
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < tmp.size(); i++) {
        int cur = tmp[i];
        if (prev != cur) {
            if (cnt >= 4) {
                for (int j = 1; j <= cnt; j++) {
                    tmp[i - j] = 0;
                }
                ans[prev] += cnt;
                cnt = 1;
                prev = cur;
                res = true;
            } else {
                cnt = 1;
                prev = cur;
            }
        } else {
            cnt++;
        }
    }
    // 마지막꺼
    if (cnt >= 4) {
        ans[tmp.back()] += cnt;
        for (int j = 1; j <= cnt; j++) {
            tmp[tmp.size() - j] = 0;
        }
    }

    // 다시 board에 push
    int idx = 0;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            board[i][j] = 0;
    for (int v : tmp) {
        if (v == 0) continue;
        int x = coord[idx].first;
        int y = coord[idx].second;
        board[x][y] = v;
        idx++;
    }
    // printBoard();
    return res;
}

void changeMarble() {
    // 1. board -> vector
    vector<int> tmp;

    for (pair<int, int> cur : coord) {
        int x = cur.first;
        int y = cur.second;
        if (board[x][y] == 0) continue;

        tmp.push_back(board[x][y]);
    }

    // 2. group -> marble A and B
    vector<int> changed;
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < tmp.size(); i++) {
        int cur = tmp[i];
        if (prev != cur) {
            changed.push_back(cnt);
            changed.push_back(prev);
            cnt = 1;
            prev = cur;
        } else {
            cnt++;
        }
    }
    // 마지막 꺼
    changed.push_back(cnt);
    changed.push_back(prev);

    // 3. vector -> board
    int idx = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            board[i][j] = 0;
    for (int v : changed) {
        if (idx > N * N - 1) break;
        if (v == 0) continue;
        int x = coord[idx].first;
        int y = coord[idx].second;
        board[x][y] = v;
        idx++;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();

    // 1. index 벡터 채우기
    getIndexVector();

    while (M--) {
        cin >> di >> si;
        di = convertDir(di);
        // 2. 블리자드 대로 구슬 파괴
        blizzard();

        // 3. 구슬 파괴
        while (1) {
            if (destroyMarble() == false) break;
        }

        // 4. 그룹 -> 구슬 A, B로 변화
        changeMarble();
        // printBoard();
    }

    cout << ans[1] * 1 + ans[2] * 2 + ans[3] * 3 << "\n";
}

---

작년 하반기에 삼전 코테 풀 때도 이상하게 기출 문제가 한 번에 다 풀려서 자만했었는데 .. 이번에도 코테를 꽤 오래 놨음에도 불구하고 거의 한 번에 잘 풀린다..

중요한 것은 침착하게 풀기, 함수로 쪼개서 풀고 각 함수의 결과가 올바르게 나오는지 확인하기

풀다가 미심쩍은 부분있으면(이런 부분도 처리해야하나?) 꼭 기억해놓기

바둑의 복기처럼 내 선택지들 되돌아보는 게 필요