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

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

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

문제 설명

문제의 자세한 설명은 위 링크를 참조하시길 바랍니다.

이 문제는 구현 시뮬레이션 문제로, 문제에서 요구하는 사항이 꽤 많고 상세합니다. 

빠짐없이 체크하여 어떻게 구현해야 할지 구상한 후에 구현해야 하는 문제입니다.

---

풀이 과정

① 먼저 초기의 파이어볼을 입력받은 후에 fireball라는 큐와 graph의 각 칸에 파이어볼을 삽입합니다.

fireball 큐는 현재 존재하는 파이어볼의 위치를 저장하는 큐이고

graph는 N x N 그래프(맵 전체)를 나타냅니다.

이 때, graph의 각 칸에는 그 칸에 존재하는 모든 파이어볼의 정보(질량, 방향, 속력)를 저장합니다.

 

② 파이어볼을 큐에서 꺼냅니다.

꺼낸 파이어볼의 칸으로 가서 파이어볼 정보를 꺼낸 후(pop) 이 정보를 토대로 파이어볼을 이동 시킵니다.

(이동은 옮길 칸에 정보(m, s, d)를 넣어줍니다.)

이 때, 아직 파이어볼이 합쳐질지 말지는 모르기 때문에 파이어볼큐에는 파이어볼을 넣지 않습니다.

 

③ 이동이 끝난 후, 파이어볼이 2개 이상 존재하는 칸은

문제에서 제시한 규칙대로 파이어볼을 하나로 합친 후에 4개로 나눕니다.

 

④ 나누어졌다면 바뀐 정보를 다시 해당 칸에 넣어주고, 위치는 fireball 큐에 삽입합니다.

 

⑤ 파이어볼이 1개만 존재하는 칸은 그대로 다시 파이어볼에 삽입합니다.

 

② ~ ⑤ 과정을 K번 반복한 후 정답을 출력하면 됩니다.

from collections import deque

n, m, k = map(int, input().split())
graph = [[deque() for _ in range(n)] for _ in range(n)]

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
fireball = deque()

for i in range(m):
    r, c, m, s, d = map(int, input().split())
    fireball.append([r-1, c-1])
    graph[r-1][c-1].append(deque([m, s, d]))

for _ in range(k):
    for j in range(len(fireball)):
        r, c = fireball.popleft()
        m, s, d = graph[r][c].popleft()
        nr = (r + s*dx[d]) % n
        nc = (c + s*dy[d]) % n
        graph[nr][nc].append(deque([m, s, d]))

    for i in range(n):
        for j in range(n):
            if len(graph[i][j]) > 1:
                sum_m, sum_s, odd_d, even_d, cnt = 0, 0, 0, 0, 0
                while graph[i][j]:
                    m, s, d = graph[i][j].popleft()
                    sum_m += m
                    sum_s += s
                    cnt += 1
                    if d % 2 == 0:
                        even_d += 1
                    else:
                        odd_d += 1
                sum_m //= 5
                if sum_m == 0:
                    continue
                sum_s //= cnt
                if even_d == cnt or odd_d == cnt:
                    dir = [0, 2, 4, 6]
                else:
                    dir = [1, 3, 5, 7]
                for d in range(4):
                    fireball.append([i, j])
                    graph[i][j].append(deque([sum_m, sum_s, dir[d]]))
            elif len(graph[i][j]) == 1:
                fireball.append([i, j])

answer = 0
for i in range(n):
    for j in range(n):
        answer += sum(arr[0] for arr in graph[i][j])

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !