[BOJ] 20056번 마법사 상어와 파이어볼 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

처음에 헤맸던 부분이 문제 설명에서는 r,c,m,d,s순으로 설명했다가 input에서는 r,c,m,s,d순으로 주어져서 문제를 잘 이해하지 못했다. 당연히 같은 순서일거라고 생각해서 꼭 그렇진 않는 경우가 있다는 사실을 깨달았다.

추가로 문제에서 다음 부분을 정확히 이해하지 못했는데,

"격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다."

주어진 테스트 케이스를 보고 이해했다. %연산으로 가볍게 해결 가능한 부분이었다. 문제를 처음에 꼼꼼히 읽으면서 내가 이해한 부분과 제대로 이해하지 못한 부분을 정확히 인지한 것이 큰 도움이 되었다. 문제 이해에 투자하는 시간을 아끼지 말자.

추가로 관련된 변수와 함수를 객체로 묶어서 코드를 짜는게 나한테 잘 맞는 것 같다. 흩뿌려져있는 것보다 코드를 짤 때 훨씬 명확해진다.

모든 수가 짝수 또는 홀수인지 판단하는 로직을 집합안에 계속 add한 뒤 길이를 측정하는 방법으로 했는데, 꽤 괜찮은 방법 같다.

조금이라도 복잡한 로직이면 반드시 손코딩 먼저 하는 습관이 좀 정착된 것 같다. 확실히 이러니까 고려해야 될 여러 케이스가 더 잘 잡힌다.

from collections import defaultdict

class Fireball:
    dx_dy = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

    def __init__(self,r,c,m,s,d):
        # 인덱스 0부터로 들어옴
        self.r = r # 행
        self.c = c # 열
        self.m = m # 질량
        self.s = s # 속력
        self.d = d # 방향
    
    def move(self):
        # s방향으로 d만큼 이동
        dx, dy = Fireball.dx_dy[self.d]
        self.r = (self.r + self.s*dx) % N
        self.c = (self.c + self.s*dy) % N
    
    def merge_fireballs(msd_list):
        # msd_list: [(m,s,d),...]
        m_sum = sum(msd[0] for msd in msd_list)
        s_sum = sum(msd[1] for msd in msd_list)
        is_even_set = set(d%2==0 for _,_,d in msd_list) # {True}
        new_ds = [0,2,4,6] if len(is_even_set)==1 else [1,3,5,7]

        new_m = int(m_sum/5)
        new_s = int(s_sum/len(msd_list))

        if new_m == 0:
            return [] # 질량 0이면 소멸
        
        new_msd_list = []
        for new_d in new_ds:
            new_msd_list.append((new_m,new_s,new_d))

        return new_msd_list

    def __str__(self) -> str: # 디버깅용
        return f"{self.r} {self.c} {self.m} {self.s} {self.d}"

N, M, K = map(int, input().split())

fireballs = []
for _ in range(M):
    r,c,m,s,d = map(int, input().split())
    r,c = r-1,c-1 # 인덱스 0부터 하기 위해
    fireballs.append(Fireball(r,c,m,s,d))

for _ in range(K):
    # 1. 이동
    for fireball in fireballs:
        fireball.move()
    
    # 2. 같은 칸에 있는 파이어볼들 4개로 나누기
    rc_msd_dict = defaultdict(list) # {(r,c):[(m,s,d),...], ...}
    for fb in fireballs:
        r,c,m,s,d = fb.r,fb.c,fb.m,fb.s,fb.d
        rc_msd_dict[(r,c)].append((m,s,d))

    new_fireballs = []
    for rc,msd_list in rc_msd_dict.items():
        r,c = rc

        if len(msd_list) >= 2: # 2개 이상 있을때 4개로 쪼개기
            next_msd_list = Fireball.merge_fireballs(msd_list)
        else:
            next_msd_list = msd_list
        
        for m,s,d in next_msd_list:
            new_fireballs.append(Fireball(r,c,m,s,d))

    fireballs = new_fireballs

print(sum(fb.m for fb in fireballs)) # 질량합