[BOJ] 백준 20056 마법사 상어와 파이어볼

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

출처: https://www.acmicpc.net/problem/20056

 Input 

7 5 3

1 3 5 2 4

2 3 5 2 6

5 2 9 1 7

6 2 1 3 5

4 4 2 4 2

　 

 Output 

9

① 파이어볼들을 이동시킵니다.

② 이동이 끝난 후, map[][]에 파이어볼이 2개 이상인 경우에는 파이어볼을 규칙에 따라 4개로 나눕니다.

    - map[][]에 파이어볼이 1개 있는 경우에는 유지

③ K번의 명령 종료 후 남아있는 파이어볼 질량의 합을 구합니다.

▶ 해당 문제는 파이어볼의 이동을 구현하는 것과 한 격자 map[][]에 2개 이상의 파이어볼을 구현해야 합니다.

     즉, 한 격자에서 여러개의 파이어볼을 담을 수 있어야 합니다.

- map[][] 안에 별도의 리스트를 두었으며, 시간 효율을 위해서

  map[][].list의 파이어볼 질량 합과 스피드 합을 별도 변수로 관리

- 파이어볼 방향의 홀수 개수(oddCnt), 짝수 개수(evenCnt) 처리를 getNextDirection()으로 구현

  (list 안에 짝수 방향 존재 / 홀수 방향 존재 → True / False 해서 판단도 가능)

 

파이어볼의 이동

상하좌우는 짝수에 해당되고, 대각선은 로 홀수번째에 해당합니다.

문제에서 "1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다."

즉, ① → ④ → ⑤로 순환되는 것이 아니라

     ① → ②  → ③ → ④ → ⑤로 순환됩니다.

      ex) (4, 4)에 위치에서 출발하여 우측 상단(1) 방향으로 3번 움직이는 경우

            : (4, 4) → (3, 5) → (2, 6) 범위 초과 → (2, 1)

               N번 만큼 이동한 경우에는 처음 위치로 돌아오는 cycle 형태입니다

이를 파이어볼의 속력만큼 한칸씩 이동하며, 범위를 벗어나는 경우 순환되도록 처리할 수 있습니다.

void moveFireball() {
    // que에 담겨있는 파이어볼 이동
    while (!que.empty()) {
        Node cur = que.front(); que.pop();
        for (int i = 0; i < cur.s; ++i) {
            cur.r += dr[cur.d];
            cur.c += dc[cur.d];
            if (cur.r > N) cur.r = 1; if (cur.c > N) cur.c = 1;
            if (cur.r < 1) cur.r = N; if (cur.c < 1) cur.c = N;
        }
        
        // 변경된 위치 (방향, 속력, 질량 유지)
        map[cur.r][cur.c].push(cur);
    }
}

하지만 map[][]의 최대 크기는 50 × 50, 각 파이어볼의 속력은 1 ≤ si ≤ 1,000 이기 때문에

경우에 따라서는 같은 구간을 왕복하여 비효율적입니다.

* 파이어볼 이동은 속력 % N 만큼만 진행하면 됩니다.

   (같은 격자에 파이어볼이 2개 이상 있을 때, 속력 = ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋로

      원래 속도를 이용해서 분리하므로 기존 속도값 자체를 변경하는 것은 좋지 않습니다.)

- 수치를 조절하고 범위를 벗어나는 경우에는 ±N을 해서 처리할 수 있습니다.

  ex) 50×50 map[][]에서 (1, 45)위치한 파이어볼이 오른쪽(2)으로 30만큼 이동하는 경우

         : (1, 45) → (1, 45 + 30) → (1, 45 + 30 - N) → (1, 75 - 50) = (1, 25)

 

한 격자에 2개 이상 파이어볼이 존재하며, 방향을 구한 후에는

divideDir[홀수/짝수][4]로 해서 파이어볼을 추가적으로 que에 push 합니다.

---

#include <stdio.h>
#include <queue>
using namespace std;

const int dr[] = { -1, -1, 0, 1, 1,  1,  0, -1 };
const int dc[] = {  0,  1, 1, 1, 0, -1, -1, -1 };
const int divideDir[2][4] = { { 1, 3, 5, 7 }, { 0, 2, 4, 6 } };
int N, M, K, ans;
struct Node {
    int r, c, m, s, d;
    void setPosition(int r, int c) {
        this->r = r, this->c = c;
    }
};
queue<Node> que;
struct Map{
    int oddCnt, evenCnt;
    int totalMass, totalSpeed;
    queue<Node> list;

    void push(Node fireball) {
        if (fireball.d % 2) oddCnt++;
        else evenCnt++;
        totalMass += fireball.m;
        totalSpeed += fireball.s;
        list.push(fireball);
    }

    void reset() {
        oddCnt = evenCnt = totalMass = totalSpeed = 0;
        list = {}; // list 비우기
    }

    int getNextDirection() {
        // list 안의 파이어볼 방향이 모두 홀수이거나 짝수
        if (oddCnt == list.size() || evenCnt == list.size()) return 1;
        return 0;
    }
}map[52][52];

void divideFireball() {
    // map[][]에서 파이어볼 개수에 따른 처리
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (map[i][j].list.size() == 0) continue;
            if (map[i][j].list.size() == 1) {
                que.push(map[i][j].list.front());
                map[i][j].list.pop();
                continue;
            }

            // map[i][j].list에 2개이상이 존재하는 경우
            int mass = map[i][j].totalMass / 5;
            if (mass <= 0) continue;
            int speed = map[i][j].totalSpeed / map[i][j].list.size();
            // list안에 있는 파이어볼의 방향에 따른 처리
            int dir = map[i][j].getNextDirection();
            for (int nd = 0; nd < 4; ++nd) {
                que.push({ i, j, mass, speed, divideDir[dir][nd]});
            }
        }
    }
}

void moveFireball() {
    // que에 담겨있는 파이어볼 이동
    while (!que.empty()) {
        Node cur = que.front(); que.pop();
        for (int i = 0; i < cur.s; ++i) {
            cur.r += dr[cur.d];
            cur.c += dc[cur.d];
            if (cur.r > N) cur.r = 1; if (cur.c > N) cur.c = 1;
            if (cur.r < 1) cur.r = N; if (cur.c < 1) cur.c = N;
        }
        
        // 변경된 위치 (방향, 속력, 질량 유지)
        map[cur.r][cur.c].push(cur);
    }
}

void reset() {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            map[i][j].reset();
        }
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    int r, c, m, s, d;
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < M; ++i) {
        scanf("%d %d %d %d %d", &r, &c, &m, &s, &d);
        que.push({ r, c, m, s, d });
    }

    for (int i = 0; i < K; ++i) {
        moveFireball();
        divideFireball();
        reset();
    }

    while (!que.empty()) {
        ans += que.front().m;
        que.pop();
    }
    printf("%d\n", ans);
}