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

출처 : 백준, https://www.acmicpc.net/problem/20056

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

# n x n의 격자, m개의 파이어볼
# 1:n은 연결되어있다
# 파이어볼은 r, c, m, d, s의 정보로 주어진다
    # 1 ≤ ri, ci ≤ N -> 1부터 시작함.
# d는 0~7까지 12시 기준 시계 방향 8방향, s는 한번 움직이는 칸 수
# 이동이 모두 끝나고, 2개 이상의 파이어볼이 같은 칸에 있다면
    # 모두 합친 후 4개로 나뉜다.
    # 질량은 질량합 // 5
    # 속력은 속력합 / 개수
    # 방향은 파이어볼의 방향이 모두 짝수거나 모두 홀수면 0, 2, 4, 6, 아니면 1, 3, 5, 7
    # 질량이 0이면 소멸

# K번 명령 이후, 남아있는 파이어볼의 질량의 합

---

 

풀이

 

from collections import defaultdict

DIRECTION = dict([[0, (-1, 0)], [1, (-1, 1)], [2, (0, 1)], [3, (1, 1)], 
                  [4, (1, 0)], [5, (1, -1)], [6, (0, -1)], [7, (-1, -1)]])

class Fireball:
    def __init__(self, mass, direction, speed):
        self.mass = mass
        self.direction = direction
        self.speed = speed

def solution(n, m, k, fireball_info_list):
    # 파이어볼이 있는 좌표
    # 여기서 좌표를 pop해서 fireball 정보에 맞게 이동시킨 후 다시 넣는다
    fireball_location = defaultdict(lambda : [])

    for info in fireball_info_list:
        r, c, m, s, d = info
        fireball_location[(r - 1, c - 1)].append(Fireball(m, d, s))

    # k번 반복 while
    while k > 0:
        # 파이어볼 이동
        move_fireball_location = defaultdict(lambda : [])

        # fireball_location에서 좌표와 파이어볼 list를 꺼낸다
        for point, fireball_list in fireball_location.items():
            # 파이어볼 리스트에서 파이어볼을 pop하고 이동시킨다.
            # 이동한 곳에서 다시 이동하는건 안됨. -> 다시 만든다

            while len(fireball_list) > 0:
                fireball = fireball_list.pop()

                dr, dc = DIRECTION[fireball.direction]
                fr, fc = point

                nr, nc = (fr + dr * fireball.speed) % n, (fc + dc * fireball.speed) % n

                # 새로운 좌표에 추가한다.
                move_fireball_location[(nr, nc)].append(fireball)

        # 2개 이상 있는 파이어볼 처리
        for point, fireball_list in move_fireball_location.items():
            if len(fireball_list) < 2:
                continue
            # 내부의 파이어볼들을 분리하거나 소멸시킨다.

            total_mass = 0
            total_speed = 0
            odd_count = 0
            even_count = 0

            while len(fireball_list) > 0:
                fireball = fireball_list.pop()

                total_mass += fireball.mass
                total_speed += fireball.speed
                if fireball.direction % 2 == 0:
                    even_count += 1
                else:
                    odd_count += 1

            each_mass = total_mass // 5
            each_speed = total_speed // (odd_count + even_count)

            if each_mass == 0: # 질량이 0이면 무시
                continue

            # 방향 구분
            each_dir = [0, 2, 4, 6] if even_count == 0 or odd_count == 0 else [1, 3, 5, 7]

            # 4개 생성 후 point에 삽입
            for i in range(4):
                move_fireball_location[point].append(Fireball(each_mass, each_dir[i], each_speed))

        # 업데이트
        fireball_location = move_fireball_location
        k -= 1  # 횟수 감소

    mass_list = []
    for fireball_list in fireball_location.values():
        for fireball in fireball_list:
            mass_list.append(fireball.mass)

    return sum(mass_list)


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

print(solution(n, m, k, fireball_info_list))

---

알게 된 점

Python 음수 나눗셈의 몫과 나머지

print(16 / 3)     # 5
print(16 // 3)    # 5
print(16 % 3)     # 1

print(-16 / 3)    # -5.33333...
print(-16 // 3)   # -6           나눗셈 한 값보다 작은 수 중 가장 큰 정수
print(int(-16/3)) # -5           우리가 기대하는 음수 나눗셈의 몫
print(-16 % 3)    # 2            Python에서 음수 나눗셈은 양수만 나옴

파이썬에서는 음수 나눗셈을 할 때 몇가지 주의사항이 필요하다.

 

- 음수 나눗셈의 몫

파이썬에서 음수 나눗셈의 경우 나눗셈한 값보다 작은 수 중 가장 큰 정수가 나온다.

-16 / 3의 몫은 -5라고 기대하지만, 실제 값은 -6으로 나온다. 

따라서 보통 우리가 기대하는 결과값을 얻기 위해서는 int 함수를 사용해야한다.

 

- 음수 나눗셈의 나머지

파이썬에서 음수 나눗셈의 나머지는 무조건 양수로 나온다.

예를 들어 -16 / 3은 몫은 -5에 나머지 -1이라 예상하지만, 실제로 몫은 -6에 나머지가 2로 나온다.

console.log(-16 % 3) // -1      js는 음수가 나온다.

JS에서는 -1로 음수로 나오는 것을 확인할 수 있다.

 

배열을 벗어나는 idx 편하게 계산하기

 

파이썬의 이러한 특성을 이용하면, 범위를 벗어나는 배열 idx를 편하게 구할 수 있다.

예를 들어, 기존 (r, c)에서 (dr * s, dc * s) 만큼 이동한 후의 배열 idx를 찾는다고 생각하자.

이를 

nr = (r + dr * s) % n
nc = (r + dr * s) % n

위와 같이 구할 수 있다.

파이썬의 나머지 연산은 무조건 양수로 나오기 때문에 결과값은 n보다 작은 양수가 나오게 된다.

이를 통해 다음 접근해야하는 idx를 편하게 구할 수 있다.

 

고찰

 

디버깅용 출력 함수

 

def drawMap(fireball_location, n):
    draw_map = [[[] for _ in range(n)] for _ in range(n)]

    for point, fireball_list in fireball_location.items():
        for fireball in fireball_list:
            i, j, = point
            draw_map[i][j].append(fireball.mass)

    for i in range(n):
        for j in range(n):
            if len(draw_map[i][j]) > 0:
                print('%10s' % ','.join(map(str, draw_map[i][j])), end='|')
            else:
                print('%10s' % ' ', end= '|')
        print()
    print('----------------------------------------------')

 

구현 문제라면, 디버깅용 출력 함수를 마련해놓는게 빠른 해결의 필수요소 같다.

결국 일일이 확인해서 정상적으로 이동하는지 체크해야하기 때문에...

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들