[백준, 삼성 기출] 20056_마법사 상어와 파이어볼 (Python)

20056_마법사 상어와 파이어볼 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 20056번: 마법사 상어와 파이어볼

1. 기록

• 22/04/24 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from copy import deepcopy

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

# graph에 상어가 있는 경우 [m, s, d] 로 저장하기
for _ in range(m):
    r, c, m, s, d = map(int, input().split())
    if m != 0:
        graph[r - 1][c - 1].append([m, s, d])

dirs = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]

for _ in range(k):
    n_graph = [[[] for _ in range(n)] for _ in range(n)]

    # 1. 모든 파이어볼이 이동한다.
    for x in range(n):
        for y in range(n):
            if graph[x][y] != []:
                for b in range(len(graph[x][y])):
                    nm, ns, nd = graph[x][y][b]
                    nx = x + dirs[nd][0] * ns
                    ny = y + dirs[nd][1] * ns

                    nx = (nx + n) % n
                    ny = (ny + n) % n

                    n_graph[nx][ny].append([nm, ns, nd])

    # 2. 2개 이상의 파이어볼이 있는 칸을 찾아 4개의 파이어볼을 만든다.
    for x2 in range(n):
        for y2 in range(n):
            if len(n_graph[x2][y2]) > 1:
                cm, cs, cd = 0, 0, []
                cnt = len(n_graph[x2][y2])

                for c in range(cnt):
                    cm += n_graph[x2][y2][c][0]
                    cs += n_graph[x2][y2][c][1]
                    cd.append(n_graph[x2][y2][c][2] % 2)
                cm = int(cm / 5)
                cs = int(cs / cnt)
                n_graph[x2][y2] = []

                if cm != 0:  # 질량이 0 인 경우 소멸하는 조건 고려
                    if sum(cd) == 0 or sum(cd) == cnt:  # 합쳐지는 파이어볼 방향이 모두 홀수거나 짝수인 경우
                        for i in range(4):
                            n_graph[x2][y2].append([cm, cs, i * 2])
                    else:
                        for j in range(4):
                            n_graph[x2][y2].append([cm, cs, j * 2 + 1])

    graph = deepcopy(n_graph)

# 남아있는 파이어볼 질량의 합 구하기
sum_m = 0
for x in range(n):
    for y in range(n):
        if graph[x][y] != []:
            for b in range(len(graph[x][y])):
                sum_m += graph[x][y][b][0]
print(sum_m)

(4) 정리

내가 놓친 부분
주어진 파이어볼의 정보를 graph 상에 잘 옮겨 놨으나
파이어 볼 이동을 한개씩을 graph 상에 옮기고 파이어볼을 나누고 옮기고 나누고해서 계속 실패했습니다.
파이어 볼이 이동한 위치, m,s,d 등을 다른 3차원 배열상에 전체를 옮겨놓은 뒤에
파이어 볼을 전체를 4방향으로 나누는 과정을 진행해야 합니다.
따라서 이러한 문제에서 deepcopy 등이 자주 사용됨을 기억하면 좋을 것 같습니다.★

(5) 참고

가장 이해가 잘된 풀이