[알고리즘/구현] 20056번 : 마법사 상어와 파이어볼 - python

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

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

 

---

• 문제
• 소요시간: 1시간 28분 

 

---

• 설계하기(접근방법) 

1. 입력받기

파이어볼을 입력받는다

 

2. 구현하기

먼저 이동을 수행해준다

같은 지점에 여러개의 파이어볼이 존재할 수 있으니

이중 리스트의 형태로 넣어줄 것이다

 

그 후 파이어볼이 2개 이상인 위치에 대해서 

문제의 요구사항을 수행해준다

 

방향은

dx dy 형태로 나타내어 배열 순환을 쉽게 해준다

그리고 범위를 벗어나는 연산에 대해서는

% 처리를 해주면 쉽게 좌표를 나타낼 수 있다

 

기존의 파이어볼 graph와

이동 후 파이어볼 new graph를 선언해주고

 

이동 후 파이어볼 분열된 결과는 다시 graph의 넣는 형태로 연산을 하면

편리하게 구현할 수  있다

 

 

 

3. 출력하기

명령 후 파이어볼 질량을 출력한다

 

 

---

• 코드(출력)

import sys
input = sys.stdin.readline

n , fireball , order = map(int, input().split())

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

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

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(order):
    new_graph = [[[] for _ in range(n)] for _ in range(n)]
    # 이동 수행
    for i in range(n):
        for j in range(n):
            if len(graph[i][j]) != 0:
                while graph[i][j]:
                    ## 질량, 속도, 방향
                    m, s, d = graph[i][j].pop()
                    nx = i + dx[d] * s
                    ny = j + dy[d] * s
                    nx = nx % n
                    ny = ny % n
                    new_graph[nx][ny].append([m, s, d])
    # 파이어볼 생성
    for i in range(n):
            for j in range(n):
                if len(new_graph[i][j]) > 1:
                    total_m = 0
                    total_s = 0
                    total_d = []
                    while new_graph[i][j]:
                        m, s, d = new_graph[i][j].pop()
                        total_m += m
                        total_s += s
                        total_d.append(d)
                    ## 새로운 질량, 속도
                    next_m = total_m // 5
                    if next_m == 0:
                        pass
                    else: 
                        next_s = total_s // len(total_d)
                        checker = 0
                        num = total_d.pop()
                        # 짝수 검사
                        if num % 2 == 0:
                            while total_d:
                                next_num = total_d.pop()
                                if next_num % 2 == 0:
                                    continue
                                else:
                                    checker = 1
                                    break
                        # 홀수 검사
                        else:
                            while total_d: 
                                next_num = total_d.pop()
                                if next_num % 2 == 1:
                                    continue
                                else:
                                    checker = 1
                                    break
                        if checker == 0:
                            for k in range(4):
                                graph[i][j].append([next_m, next_s, k * 2])
                        else:
                            for k in range(4):
                                graph[i][j].append([next_m, next_s, (k * 2 + 1)])
                elif len(new_graph[i][j]) == 1:
                    graph[i][j].append(new_graph[i][j].pop())
              
total_fireball = 0

for i in range(n):
    for j in range(n):
        if len(graph[i][j]) != 0:
                while graph[i][j]:
                    # print(graph[i][j])
                    m, s, d = graph[i][j].pop()
                    total_fireball += m

print(total_fireball)

---

• 얻어갈 부분

1. new_graph와 graph, 이중배열인데 graph[i][j]가 아닌 graph로 접근해서 오류가 좀 있었다. 디버깅할 때 주의하자