[백준] 20056번 마법사 상어와 파이어볼 파이썬 풀이 (+ 새 정답 코드 추가)

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

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

---

1. 접근 방식

• 이동할 때의 핵심은 「격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.」이다.

연결되어 있는 격자

예를 들어 파이어볼로 (4, 1, 2, 5, 7)을 입력 받았다면, 실제 테이블의 3행 0열에 해당 파이어볼이 존재하는 것이다.

속도 5, 방향 7.즉, 좌측 상향 대각선으로 5칸 이동해야 하므로 파이어볼은 총 (-5, -5)만큼 이동해야 한다. 그럼 (3, 0) + (-5, -5) = (-2, -5)인데, (-2, -5)는 어디일까?

위 그림에서 알 수 있듯이 (-2, -5)는 최종적으로 2행 3열이다. 격자가 연결되어 있기 때문에 -1열은 곧 3열이고, -1행 역시 3행으로 이어지는 것이다.

이를 수식으로 나타내면 { (3, 0) + (-5, -5) } % (4, 4)이다. (이때 4는 격자의 크기)

 

• 2중 리스트로 격자를 표현하자.

격자를 2중 리스트로 표현하므로, 이중 for문으로 격자를 순회하면서 각 칸의 파이어볼 개수를 확인한다. 2개 이상의 파이어볼이 한 칸에 들어갈 수 있으므로, 내부 리스트의 원소를 리스트로 만들어야 한다.

board = [[[] for _ in range(n)] for _ in range(n)]

 

• 한 칸에 2개 이상의 파이어볼이 있을 경우, 「합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.」에 주의하자.

ⓐ 합쳐진 파이어볼의 방향이 "모두" 짝수이거나, 홀수일 때 (0, 2, 4, 6)이고, ⓑ 홀수나 짝수가 섞여 있다면 (1, 3, 5, 7)이다.

나는 이 지문을 제대로 확인하지 못하고, 모든 파이어볼의 합이 짝수면 (0, 2, 4, 6), 홀수면 (1, 3, 5, 7)이라고 문제를 풀다가 무척 고생했다...

질문 게시판을 돌아보니, 다른 분들은 방향이 모두 짝수/홀수인지를 체크하는 로직에서 실수를 많이 했었다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def move(info):
    r = (info[0] + directions[info[4]][0] * info[3]) % n
    c = (info[1] + directions[info[4]][1] * info[3]) % n

    board[r][c].append(info[2:])

def is_all_even_or_odd(ds):
    if len([d for d in ds if d % 2 == 0]) == len(ds):
        return True
    if len([d for d in ds if d % 2 == 1]) == len(ds):
        return True
    return False

# main
n, m, k = map(int, input().split())
fireballs = []
for _ in range(m):
    r, c, m, s, d = list(map(int, input().split()))
    fireballs.append([r-1, c-1, m, s, d])

board = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(k):
	# step1
    while fireballs:
        move(fireballs.pop())

	# step2
    for i in range(n):
        for j in range(n):
            if len(board[i][j]) == 1:
                fireballs.append([i, j] + board[i][j].pop())

            elif len(board[i][j]) >= 2:
                mass, speed, ds, length = 0, 0, [], 0
                while board[i][j]:
                    m, s, d = board[i][j].pop()
                    mass += m
                    speed += s
                    ds.append(d)
                    length += 1

                mass //= 5
                if mass > 0:
                    speed //= length
                    direction = (0, 2, 4, 6) if is_all_even_or_odd(ds) else (1, 3, 5, 7)

                    for d in direction:
                        fireballs.append([i, j, mass, speed, d])

# answer
print(sum(fb[2] for fb in fireballs))

 

 

 

3. 더 효율적인 새 정답 코드

 

오랜만에 이 문제를 다시 풀어보았다. 코드 길이는 기존보다 다소 길어지긴 했지만, 실행 시간이 절반 정도 줄었다.

 

• 기존 코드와 새 코드의 차이점

기존에는 기존에는 2차원 배열 board와 1차원 배열 fireballs를 사용했다. 같은 칸에 존재하는 파이어볼을 파악하기 위해  2차원 배열 board를 전체 순회하면서 특정 위치에 파이어볼의 개수가 몇 개인지 확인했다.

그러나 이번엔 dictionary 자료형을 사용하여 파이어볼의 위치를 key로, 세부 파이어볼 정보를 담은 리스트를 value로 사용하므로써 같은 칸에 존재하는 파이어볼을 파악하는 데 시간을 줄일 수 있었다.

 

def move(fbs):
    moved = dict()
    for pos in fbs:
        for fb in fbs[pos]:
            mass, speed, direction = fb
            x = (pos[0] + directions[direction][0] * speed) % n
            y = (pos[1] + directions[direction][1] * speed) % n

            if x == 0:
                x = n
            if y == 0:
                y = n

            if (x, y) in moved:
                moved[(x, y)].append((mass, speed, direction))
            else:
                moved[(x, y)] = [(mass, speed, direction)]

    return moved


def solve_conflict(fbs):
    for pos in fbs:
        if len(fbs[pos]) > 1:
            fbs[pos] = split(fbs[pos])
    return fbs


def split(fbs):
    import math

    length = len(fbs)
    tm = sum(f[0] for f in fbs)
    ts = sum(f[1] for f in fbs)

    if sum(f[2] % 2 for f in fbs) in [0, length]:
        ds = [0, 2, 4, 6]
    else:
        ds = [1, 3, 5, 7]

    mass = math.floor(tm / DIVIDE)

    if not mass:
        return []

    speed = math.floor(ts / length)
    return [(mass, speed, d) for d in ds]


def sum_mass(fbs):
    result = 0
    for pos in fbs:
        for fb in fbs[pos]:
            result += fb[0]
    return result


DIVIDE = 5
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

n, m, k = map(int, input().split())
fireballs = dict()
for _ in range(m):
    r, c, m, s, d = map(int, input().split())

    if (r, c) in fireballs:
        fireballs[(r, c)].append((m, s, d))
    else:
        fireballs[(r, c)] = [(m, s, d)]

for _ in range(k):
    moved = move(fireballs)
    fireballs = solve_conflict(moved)

print(sum_mass(fireballs))