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

문제 링크 : https://www.acmicpc.net/problem/20056

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

1. 접근 방법

빡빡한 구현이 필요한 상어 문제를 처음 접했을 때는 많이 막막했었다.

코드를 구현하는 과정뿐만 아니라, 적절한 자료구조, 알고리즘을 잘 다루지 못해서 더욱 막막했었던 것 같다.

그러나 시간이 지나고, 문제를 코드로 구현하는 과정과, 자료구조, 알고리즘을 잘 다루기 시작하며 보다 수월하게 문제를 해결하는 것 같다.

 

 

2. 풀이 코드

🖥python 코드

import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


def move_fireballs(magical_map: list) -> list:
    global n, dx, dy
    next_magical_map = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for m, s, d in magical_map[i][j]:
                ni, nj = (i + dx[d] * s) % n, (j + dy[d] * s) % n
                next_magical_map[ni][nj].append((m, s, d))
    return next_magical_map


def explode_fireballs(magical_map: list) -> list:
    global n
    next_magical_map = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if len(magical_map[i][j]) < 2:
                next_magical_map[i][j] = magical_map[i][j][::]
            else:
                # 해당 파이어볼 총 질량
                total_weights = 0
                total_speed = 0
                check_direction = []
                for m, s, d in magical_map[i][j]:
                    total_weights += m
                    total_speed += s
                    check_direction.append(d % 2)
                weight = total_weights // 5
                if weight == 0:
                    continue
                speed = total_speed // len(magical_map[i][j])
                # 방향 결정
                if all(check_direction) or not any(check_direction):
                    next_direction = [0, 2, 4, 6]
                else:
                    next_direction = [1, 3, 5, 7]
                # 다음 파이어볼 설정
                for d in next_direction:
                    next_magical_map[i][j].append((weight, speed, d))
    return next_magical_map


def count_fireballs(magical_map: list) -> int:
    global n
    fireballs = 0
    for i in range(n):
        for j in range(n):
            for m, *_ in magical_map[i][j]:
                fireballs += m
    return fireballs


n, m, k = MIIS()
magical_map = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(m):
    r, c, m, s, d = MIIS()
    magical_map[r - 1][c - 1].append((m, s, d))

dx, dy = (-1, -1, 0, 1, 1, 1, 0, -1), (0, 1, 1, 1, 0, -1, -1, -1)
for _ in range(k):
    # 모든 파이어볼 이동
    magical_map = move_fireballs(magical_map)
    # 한 칸에 파이어볼 2개 이상이면 나누어지고 다시 탐색
    magical_map = explode_fireballs(magical_map)

print(count_fireballs(magical_map))

📕풀이 방법

기본 구조는 각 파이어볼 이동 >> 모든 칸을 확인하여 파이어볼이 2개 이상일 때 합쳐진 후 나누기이다.

파이어 볼 이동은 조금 더 편하게 하기 위해 비어이있는 3차원 리스트를 만들어, 이동된 파이어볼을 넣었다.

파이어볼을 합쳐서 처리하는 과정에서는 모든 파이어볼이 짝수인지 홀수인지 판별하기 위해 all, any 함수를 사용했다.

 

 

3. 생각 정리

구현 문제는 항상 어렵게만 느껴졌다. 조건은 만고, 코드로 나타내는 것이 간단하지 않아서이다.

그런데 이제는 구현문제가 가장 쉽게 느껴질 때도 있다. 물론 일부 까다로운 조건을 다루는 것과 적절한 자료구조 활용이 어려울 때가 있지만, 문제를 잘 일고 풀어가면 보통은 틀리지 않고 잘 풀리는 것 같다.

이번 문제는 파이어볼이 있는 지도를 항상 새로 만드는 것 보다, 딕셔너리의 키로 파이어볼의 위치, 값으로 각 파이어볼의 정보를 저장하여 더욱 빠르게 해결할 수 있다. 이런 자료구조별 다양한 방법과 성능을 알아가는 것도 구현 문제의 큰 장점이라 생각한다.