[백준 20056번] 마법사 상어와 파이어볼(파이썬)

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

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

 

이 문제는 다소 불친절해서

풀기가 힘들었습니다.

보통 문제에서

예시로 어떻게 이동하는지 보여주는데

이건 그런게 없어서

개인적으론 불친절하다고 느꼈네요.

저는 접근할 때

지도에 한꺼번에

파이어볼의 좌표를 다 그리고

이동과 나누기 두 개를 시행했습니다.

그리고 이동을 할 때

복사 후 저장하는 방식을 사용했습니다.

바로 원본에서 이동하면

저렇게 잘못동작할 수 있습니다.

문제에서 요구하는 데로였다면

5와 7이 중앙으로 와서

분배하는 식인데

저렇게하면 뭔가 엉성해지죠.

물론 '결과론적으로는'같지만

다른 여러가지 케이스와 종합하면

저 방식은 잘못되었습니다.

그래서 임시저장을 만들어서 코드를 구했습니다.

 

# 백준 20056 마법사 상어와 파이어볼
import copy
import math

N, M, K = map(int, input().split())
base = [[[[], [], []] for _ in range(N)] for _ in range(N)]
for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    base[r - 1][c - 1][0].append(m)
    base[r - 1][c - 1][1].append(d)
    base[r - 1][c - 1][2].append(s)
# print(base)
# print()
# 움직이는 거 설정
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]

for Turn in range(1, K + 1):
    # print(Turn)
    tmp_base = []
    tmp_base = copy.deepcopy(base)
    # 파이어볼 이동먼저
    for r in range(N):
        for c in range(N):
            if len(base[r][c][0]) >= 1:
                index = 0
                # print(base[r][c][1])
                # 불이 몇개가 있을지 모르므로 길이에 따라서 해준다
                for k in range(len(base[r][c][0])):
                    now_fire = tmp_base[r][c][0][index]
                    d = tmp_base[r][c][1][index]
                    s = tmp_base[r][c][2][index]
                    nr = (r + dr[d] * s) % N
                    nc = (c + dc[d] * s) % N
                    # print(nr,nc)
                    """
                    if nr<0 or nr>=N or nc<0 or nc>=N:
                      if nr<0:
                        while nr<0:
                          nr+=N
                      if nr>=N:
                        while nr>=N:
                          nr-=N
                      if nc<0:
                        while nc<0:
                          nc+=N
                      if nc>=N:
                        while nc>=N:
                          nc-=N
                    """
                    tmp_base[nr][nc][0].append(now_fire)
                    tmp_base[nr][nc][1].append(d)
                    tmp_base[nr][nc][2].append(s)
                    # 이동 후 전에꺼에서 뺴준다
                    tmp_base[r][c][0].pop(index)
                    tmp_base[r][c][1].pop(index)
                    tmp_base[r][c][2].pop(index)
                    # print(index)
                    # print(tmp_base[r][c][1])

    # print(tmp_base)
    base = tmp_base
    # 파이어볼 나누기
    for r in range(N):
        for c in range(N):
            if len(base[r][c][0]) > 1:
                fire_sum = sum(base[r][c][0])
                fire_num = len(base[r][c][0])
                divide_fire = fire_sum // 5
                # 파이어볼 분배
                # 0이면 모두 사라짐.
                if divide_fire == 0:
                    base[r][c][0].clear()
                    base[r][c][1].clear()
                    base[r][c][2].clear()
                # 0이 아니라면 4개의 파이어볼로 나눔.
                else:
                    base[r][c][0].clear()
                    for _ in range(4):
                        base[r][c][0].append(divide_fire)
                    # 방향설정
                    one = 0
                    two = 0
                    for d in base[r][c][1]:
                        if d % 2 == 0:
                            two += 1
                        else:
                            one += 1
                    base[r][c][1].clear()
                    if one == fire_num or two == fire_num:
                        base[r][c][1].append(0)
                        base[r][c][1].append(2)
                        base[r][c][1].append(4)
                        base[r][c][1].append(6)
                    else:
                        base[r][c][1].append(1)
                        base[r][c][1].append(3)
                        base[r][c][1].append(5)
                        base[r][c][1].append(7)
                    # 속도설정
                    speed_sum = sum(base[r][c][2])
                    fire_speed = speed_sum // fire_num
                    base[r][c][2].clear()
                    for _ in range(4):
                        base[r][c][2].append(fire_speed)
    # print(base)
    # print()
# 모든 질량 구하기
total_sum = 0
for r in range(N):
    for c in range(N):
        if len(base[r][c][0]) > 0:
            total_sum += sum(base[r][c][0])

print(total_sum)

        
          
전 이 문제를 풀다가 해매였던 게

이 문제에서는

'좌표를 넘어가면 어떻게 되는지'

명확하게 명시가 되지 않았습니다.

처음에는 파이어볼이 사라지는 건가했다가

예시를 보니 아닌 듯해서

여러가지로 짱돌굴리다가

질문하기를 눌러서 확인하니

'범위를 벗어나면 반대편으로 나오는'

그런 구조였습니다.

이런 멘트는 좀 써주지...

 

참고로 위의 코드는

pypy3기준으로도

수행시간이 상당히 긴 편입니다.

그 이유인 즉슨

이동하고 분배할 때

전체 지도를 계속 그러놓고하다보니

탐색시간이 오래걸릴 수 밖에 없는 구조입니다.

예시야 그나마 케이스가 작았지만

케이스가 많아질수록

느리게 동작하는 코드였죠.

 

https://jennnn.tistory.com/77

[백준] 20056. 마법사 상어와 파이어볼 / python 파이썬

이런 식으로 간단하게 풀면

시간도 줄이고

코드 간결성도 좋아보입니다.

 

++++++

 

#백준 20056 마법사 상어와 파이어볼
from copy import deepcopy

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

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

for _ in range(M):
    r,c,m,s,d=map(int,input().split())
    graph[r-1][c-1].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(K):
    temp=[[[]for _ in range(N)]for _ in range(N)]
    #1. 파이어볼 이동
    for x in range(N):
        for y in range(N):
            if graph[x][y]:
                for fish in graph[x][y]:
                    f_m,f_s,f_d=fish
                    nx=(x+f_s*dx[f_d])%N
                    ny=(y+f_s*dy[f_d])%N
                    temp[nx][ny].append([f_m,f_s,f_d])


    #2. 2개 이상인 파이어볼 4개로 나누기
    #질량은 합//5
    #속력은 합/갯수
    #방향이 모두 홀수-->0 2 4 6
    #아니라면 1 3 5 7
    for x in range(N):
        for y in range(N):
            if len(temp[x][y])>=2:
                t_n=len(temp[x][y])
                t_m=0
                t_s=0
                one=0
                two=0
                for fish in temp[x][y]:
                    t_m+=fish[0]
                    t_s+=fish[1]
                    if fish[2]%2==1:
                        one+=1
                    else:
                        two+=1
                t_m//=5
                t_s//=t_n
                temp[x][y].clear()
                if t_m>0:
                    if one==t_n or two==t_n:
                        temp[x][y].append([t_m,t_s,0])
                        temp[x][y].append([t_m, t_s, 2])
                        temp[x][y].append([t_m, t_s, 4])
                        temp[x][y].append([t_m, t_s, 6])
                    else:
                        temp[x][y].append([t_m, t_s, 1])
                        temp[x][y].append([t_m, t_s, 3])
                        temp[x][y].append([t_m, t_s, 5])
                        temp[x][y].append([t_m, t_s, 7])
    graph=deepcopy(temp)

t_m=0
for x in range(N):
    for y in range(N):
        if graph[x][y]:
            for fish in graph[x][y]:
                t_m+=fish[0]

print(t_m)

개선사항

 

1. 전에는 graph를 뭉탱이로 복사했는데

그럴 필요없이

이동할 때는 temp임시 리스트에 저장

 

2. 2개의 리스트로 구현해주면서

코드의 지저분한 부분이 감소.

 

pypy3로도 느리게 통과하는 코드입니다.

위에 링크걸어준 코드로

시간최적화에 신경쓰면 좋을듯 합니다.