BOJ 20056 - 마법사 상어와 파이어볼 링크
(2024.01.07 기준 G4)

문제

크기가 N인 정사각형 격자가 있으며, 1번 행, 열은 N번 행, 열과 연결되어 있다.

마법사 상어가 질량과 속력, 방향이 주어져 있는 파이어봏 M개를 각각 다른 위치에 이동을 대기시켜 놓았다.
마법사 상어는 이동을 K번 명령하는데, 이동 한번에 다음과 같은 일들이 일어난다.

1. 모든 파이어볼은 자신의 방향 d로 속력 s칸 만큼 이동
2. 이동한 후 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일들이 일어난다.
   2-1. 모두 하나로 합쳐져서 다시 4개로 나뉜다.
   2-2. 질량은 ⌊질량의 합 / 5⌋, 속력은 ⌊(속력의 합)/(개수)⌋으로 정해진다.
   2-3. 방향이 모두 홀수이거나 짝수이면 방향은 각각 0, 2, 4, 6이 되고, 아니면 각각 1, 3, 5, 7이 된다.
3. 질량이 0인 파이어볼은 없어진다.

K번의 이동 명령 후, 남아있는 파이어볼들의 질량의 합 출력

알고리즘

지문 그대로 시뮬레이션

풀이

합치기 전과 후로 나눠서 정보를 관리해보자.

합치기 후는 각각 위치에서 각각 파이어볼을 따로 관리해주면 된다. 이동은 서로 독립적이기 때문이다.

합치기 전은 2개 이상의 파이어볼이 있는 위치에선 파이어볼을 합쳐야 한다. 그러므로 질량의 합, 속력의 합, 방향 리스트를 같이 관리해주면 된다.

1. 합치기 후에서 각 파이어볼이 이동하고 나서 합치기 전으로 보내주자.
   보낼 때, 질량과 속력은 합쳐주고, 방향은 방향 리스트에 삽입하면 된다. 그러면 방향 리스트의 size로 파이어볼의 개수도 같이 알 수 있다.

2. 합치기 전에서는, 합칠 수 있으면 합쳐서 합치기 후로 다시 보내주자.
   각 위치에서 파이어볼이 만약 하나라면 그대로 합치기 후로 보내주면 된다.
   2개 이상이라면, 질량의 합을 5로 나눠서 0인지 먼저 확인하자. 질량이 0이 되면 소멸되어 없어지기 때문이다.
   다음은 방향이 모두 홀수이거나 짝수인지 검사하자. 그리고 이에 따라 알맞은 네 방향으로 파이어볼을 알맞은 질량과 속력으로 하여금 합치기 후로 보내주면 된다.

각각 위치에서 처리가 끝나면 항상 빈칸으로 만들어주는 초기화 작업을 잊지말고 해주자.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

struct info{
    int m, s; // 질량, 속력
    vector<int> d; // 방향
    info(){
        m = s = 0;
        d.clear();
    }
};

const int MAXN = 50;
const pii dir[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; // 방향

int N, M, K;
info before[MAXN][MAXN]; // 파이어볼 합치기 전 정보
vector<tiii> after[MAXN][MAXN]; // 파이어볼 합치기 후 정보

// 파이어볼을 다음 위치로 이동
void move(int r, int c, int m, int s, int d){

    // 다음 위치
    int nr = (r + dir[d].x * s) % N;
    if (nr < 0) nr += N;
    int nc = (c + dir[d].y * s) % N;
    if (nc < 0) nc += N;

    // 합치기 전으로 정보 추가
    before[nr][nc].m += m;
    before[nr][nc].s += s;
    before[nr][nc].d.push_back(d);
}

// 파이어볼 합치기
void merge(int r, int c){

    // 질량이 0이 되는지 확인
    int m = before[r][c].m / 5;
    if (!m) return;

    // 속력
    int s = before[r][c].s / before[r][c].d.size();

    // 모든 방향이 홀수나 짝수로 일관성이 있는지 확인
    bool flag = true;
    for (int i = 1, sz = before[r][c].d.size(); i < sz; i++)
        if ((before[r][c].d[0] & 1) ^ (before[r][c].d[i] & 1)){
            flag = false;
            break;
        }

    // 파이어볼을 알맞은 방향으로 나눠서 합치기 후로 정보 추가
    if (flag) for (int d = 0; d <= 6; d += 2) after[r][c].push_back({m, s, d});
    else for (int d = 1; d <= 7; d += 2) after[r][c].push_back({m, s, d});
}

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

    cin >> N >> M >> K;
    for (int _ = M, r, c, m, s, d; _; _--){
        cin >> r >> c >> m >> s >> d;
        after[--r][--c].push_back({m, s, d});
    }

    // K번 반복
    while (K--){

        // 파이어볼을 전부 다음 위치로 옮긴다.
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++){
            for (auto [m, s, d]: after[r][c]) move(r, c, m, s, d);
            after[r][c].clear(); // 초기화
        }

        // 파이어볼을 합칠 수 있으면 합친다.
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++){
            if (before[r][c].d.empty()) continue; // 파이어볼이 없는 경우
            if (before[r][c].d.size() == 1) // 파이어볼이 하나인 경우 그대로
                after[r][c].push_back({before[r][c].m, before[r][c].s, before[r][c].d[0]});
            else merge(r, c); // 파이어볼이 여럿인 경우 합치기
            before[r][c] = info(); // 초기화
        }
    }

    // 질량의 합 출력
    int result = 0;
    for (int r = 0; r < N; r++) for (int c = 0; c < N; c++)
        for (auto [m, s, d]: after[r][c]) result += m;

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

# 파이어볼을 다음 위치로 이동
def move(r, c, m, s, d):

    # 다음 위치
    nr = (r + dir[d][0] * s) % N
    nc = (c + dir[d][1] * s) % N

    # 합치기 전으로 정보 추가
    before[nr][nc][0] += m
    before[nr][nc][1] += s
    before[nr][nc][2].append(d)

# 파이어볼 합치기
def merge(r, c):

    # 질량이 0이 되는지 확인
    m = before[r][c][0] // 5
    if not m:
        return

    # 속력
    s = before[r][c][1] // len(before[r][c][2])

    # 모든 방향이 홀수나 짝수로 일관성이 있는지 확인
    flag = True
    for i in range(1, len(before[r][c][2])):
        if (before[r][c][2][0] & 1) ^ (before[r][c][2][i] & 1):
            flag = False
            break

    # 파이어볼을 알맞은 방향으로 나눠서 합치기 후로 정보 추가
    if flag:
        for d in [0, 2, 4, 6]:
            after[r][c].append((m, s, d))
    else:
        for d in [1, 3, 5, 7]:
            after[r][c].append((m, s, d))

# 방향
dir = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

N, M, K = map(int, input().split())
before = [[[0, 0, []] for _ in range(N)] for _ in range(N)] # 파이어볼 합치기 전 정보 (질량, 속도, 방향)
after = [[[] for _ in range(N)] for _ in range(N)] # 파이어볼 합치기 후 정보

for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    after[r - 1][c - 1].append((m, s, d))

# K번 반복
for _ in range(K):

    # 파이어볼을 전부 다음 위치로 옮긴다.
    for r in range(N):
        for c in range(N):
            for m, s, d in after[r][c]:
                print(r, c, m, s, d)
                move(r, c, m, s, d)
            after[r][c] = [] # 초기화

    # 파이어볼을 합칠 수 있으면 합친다.
    for r in range(N):
        for c in range(N):
            if not before[r][c][2]: # 파이어볼이 없는 경우
                continue
            if len(before[r][c][2]) == 1: # 파이어볼이 하나인 경우 그대로
                after[r][c].append((before[r][c][0], before[r][c][1], before[r][c][2][0]))
            else: # 파이어볼이 여럿인 경우 합치기
                merge(r, c)
            before[r][c] = [0, 0, []] # 초기화

# 질량의 합 출력
result = 0
for r in range(N):
    for c in range(N):
        for m, s, d in after[r][c]:
            result += m

print(result)