백준_20056_마법사 상어와 파이어볼(python)

※ 접근법

입력제한에서 N의 최대 크기는 50이었고 k의 최대 크기는 1000이었기 때문에 문제에서 시키는대로만 구현하면 된다.

 

※ 풀이

1. defaultdict(list)인 사전형을 두개 만들었다.

2. 사전형의 키는 좌표 값이었고 좌표 값은 변하지 않을 것이기에 튜플 형태로 지정했다. value값은 질량,속도,방향순서대로 리스트 형태로 삽입했다.

3. k의 크기만큼 start(파이어볼 움직임), check(파이어볼이 두개 이상 뭉쳐있는지)를 실행해줬다.

4. start()함수는 매우 간단한데 dic에서 key를 하나씩 꺼내서 파이어볼을 이동시켜준다.

5. check() 함수도 문제에서 시키는 대로만 하면 되는 간단한 함수이다.

6. 문제 알고리즘 유형 자체가 구현, 시뮬레이션으로 구분 되기 때문에 시키는대로만 잘 따라하면 된다.

 

※ 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())

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

dic = defaultdict(list)
ch_dic = defaultdict(list)

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

def start():
    for sr,sc in dic.keys():
        for fb in dic[(sr,sc)]:
            nx = (sr + dx[fb[2]] * fb[1]) % n
            ny = (sc + dy[fb[2]] * fb[1]) % n    
            ch_dic[(nx,ny)].append([fb[0],fb[1],fb[2]])
    dic.clear()

def check():
    for start_r,start_c in ch_dic.keys():
        if len(ch_dic[(start_r,start_c)]) > 1:
            mc,sc,even,odd = 0,0,0,0
            for fb in ch_dic[(start_r,start_c)]:
                mc += fb[0]
                sc += fb[1]
                if fb[2] % 2 == 0:
                    even += 1
                else:
                    odd += 1
            if mc // 5 != 0:
                fm = mc // 5
                cnt = len(ch_dic[(start_r,start_c)])
                fs = sc // cnt
                if even == cnt or odd == cnt:
                    fd = [0,2,4,6]
                else:
                    fd = [1,3,5,7]
                for i in fd:
                    dic[(start_r,start_c)].append([fm,fs,i])
            else:
                continue
        else:    
            dic[(start_r,start_c)].append([ch_dic[(start_r,start_c)][0][0],ch_dic[(start_r,start_c)][0][1],ch_dic[(start_r,start_c)][0][2]])
    ch_dic.clear()

for i in range(k):
    start() 
    check()

answer = 0
for sr,sc in dic.keys():
    for fb in dic[(sr,sc)]:
        answer += fb[0]
print(answer)

 

※ 회고

 처음에 접근법에서 써놓은 것처럼 구현만 했다가 바로 시간 초과가 났다. 이유는 간단하다 m,s,d 하나마다 리스트를 만들었기 때문이다. defaultdict함수 안에 list가 들어갈 수 있다는 것도 처음 알았고 key값으로 튜플이 들어갈 수 있고 value 값으로 이중리스트가 들어갈 수 있다는 것도 배웠다. 여담이지만, 이런 타입의 자율성 때문에 C언어에서 python으로 넘어왔다. 가끔 같은 로직인데 python이 C계열 언어에 비해 시간이 오래 걸리는 것을 보면 부럽지만 장단점이 있는 것이니 python의 이점을 활용해서 극복해보자!!!