백준: 20056 마법사 상어와 파이어볼

문제

20056번: 마법사 상어와 파이어볼

 

문제 풀이

 입력값으로 파이어볼의 위치 (r, c), 질량(m), 방향(d), 속력(s)이 주어진다. 시뮬레이션 문제이므로 다음과 같은 과정을 순차적으로 진행한다.

 

• 모든 파이어볼은 자신의 방향으로 속력만큼 이동한다.
• 이동을 마친 후, 이동된 파이어볼들이 같은 칸에 2개 이상 있다면 다음과 같이 처리한다.
  • 파이어볼은 4개로 나누어진다.
  • 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
    • 질량은 `합쳐진 파이어볼 질량의 합 / 5`이다.
    • 속력은 `합쳐진 파이어볼 속력의 합 /  합쳐진 파이어볼의 개수`이다.
    • 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 `0, 2, 4, 6`이 된다.
      • 아니라면 `1, 3, 5, 7`이 된다.
  • 질량이 0인 파이어볼은 소멸되어 없어진다.

위와 같은 시뮬레이션을 K번 수행한 후, 남아있는 파이어볼 질량의 합을 구해서 출력하면 정답을 찾을 수 있다.

 

 

코드

from sys import stdin
from copy import deepcopy

X = 0
Y = 1
M = 2
S = 3
D = 4


def move_fire_ball():
    global board

    for idx, info in enumerate(fire_ball):
        dx, dy = dirs[info[D]]
        # 자신의 방향의 속도 만큼 이동하므로 현재 위치 + 방향 * 속도
        # 격자의 행과 열은 연결되어 있으므로, %로 위치를 찾음
        next_x, next_y = (info[X] + dx * info[S]) % n, (info[Y] + dy * info[S]) % n

        if board[next_x][next_y] is None:
            board[next_x][next_y] = [idx]
        else:
            board[next_x][next_y].append(idx)

        info[X], info[Y] = next_x, next_y


def calc_file_ball(temp, fireballs, loc):
    # 질량과 속도의 합
    sum_m, sum_s = 0, 0
    even, odd = True, True

    for idx in fireballs:
        sum_m += fire_ball[idx][M]
        sum_s += fire_ball[idx][S]

        if not fire_ball[idx][D] % 2:
            odd = False
        else:
            even = False

    cal_m = sum_m // 5
    cal_s = sum_s // len(fireballs)

    # 질량이 없는 경우에는, 아래와 같은 연산이 필요 없음
    if cal_m:
        x, y = loc

        # mp -> multiplier
        for mp in range(4):
            # 파이어볼의 방향이 모두 짝수나 홀수인 경우 (0, 2, 4, 6)
            if even or odd:
                temp.append([x, y, cal_m, cal_s, 2 * mp])
            # 아닌 경우 (1, 3, 5, 7)
            else:
                temp.append([x, y, cal_m, cal_s, 2 * mp + 1])


def sum_fire_ball():
    global fire_ball
    temp = []

    for x in range(n):
        for y in range(n):
            # 해당 위치에 fireball이 없는 경우
            if board[x][y] is None:
                continue
            # 헤딩 위치에 fireball이 하나인 경우
            elif len(board[x][y]) == 1:
                cur_idx = board[x][y][0]
                temp.append(fire_ball[cur_idx])
            # 해당 위치에 fireball이 두 개 이상인 경우
            else:
                calc_file_ball(temp, board[x][y], (x, y))
            board[x][y] = None

    fire_ball = deepcopy(temp)


if __name__ == '__main__':
    n, m, k = map(int, stdin.readline().split())

    # 8방향으로 이동이 필요하므로
    dirs = ((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1))
    board = [[None] * n for _ in range(n)]
    fire_ball = [None] * m

    for idx in range(m):
        cur_info = list(map(int, stdin.readline().split()))
        cur_info[X] -= 1
        cur_info[Y] -= 1
        fire_ball[idx] = cur_info

    for _ in range(k):
        move_fire_ball()
        sum_fire_ball()

    print(sum(map(lambda x: x[M], fire_ball)))