[Python] 백준_마법사 상어와 비바라기(21610)

문제

 

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

21610번: 마법사 상어와 비바라기

 

 

풀이

 

구현만 하면 되는 문제였다. 다만 시간초과를 해결하느라 오래걸렸다.

 

문제의 조건 그대로, 

 

구름을 먼저 이동시키고 물을 1씩 추가해줬다. 다음으로 대각선을 확인하여 물복사버그를 실행해주었다. 

 

이후엔 다시 반복문을 통해 한칸씩 확인하며 물의 양이 2보다 많고, 이전에 구름이 아니었는지 확인 후에 temp에 넣어 cloud를 temp로 초기화시켜주었다.

 

마지막으로 다시 한 칸씩 확인하며 물의 양을 더해주었다.

 

 

처음에는 deque를 쓰지않고 그냥 list를 이용하였다. 그러다보니 구름의 위치를 이동하는 과정에서 맨 앞의 것을 빼고 뒤에 추가할 때 pop(0)를 사용하게되어 시간이 오래걸렸다. deque을 이용해서 popleft()를 이용해 시간복잡도를 줄여주었다.

다음으로는 이전에 구름이었는지 확인할때 in을 이용하여 cloud안에 있는지 확인하였다. 이렇게하면 O(n)이기때문에 check라는 리스트를 이용하여 시간복잡도를 O(1)로 줄였다.

 

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())

basket = []
cloud = [(n-1,0),(n-1,1),(n-2,0),(n-2,1)]
cloud = deque(cloud)
def copyWater(cloud):
    D = [(1,1),(1,-1),(-1,1),(-1,-1)]
    for point in cloud:
        for i in range(4):
            newX = point[0] + D[i][0]
            newY = point[1] + D[i][1]
            if newX < 0 or newY < 0 or newX >= n or newY >= n:
                continue
            if basket[newX][newY] != 0:
                basket[point[0]][point[1]] += 1
def magic(d,s):
    global cloud
    D = [(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1)]
    for _ in range(len(cloud)):
        x,y = cloud.popleft()
        tempX = x + (D[d - 1][0] * s)
        tempY = y + (D[d - 1][1] * s)
        if tempX < 0:
            tempX += n
        if tempY < 0:
            tempY += n
        newX = tempX % n; newY = tempY % n
        cloud.append((newX,newY))
        basket[newX][newY] += 1
        check[newX][newY] = 1
    copyWater(cloud)
for _ in range(n):
    basket.append(list(map(int,input().split())))
for _ in range(m):
    d,s = map(int,input().split())
    check = [[0] * n for _ in range(n)]
    magic(d,s)
    temp = deque()
    for i in range(n):
        for j in range(n):
            if basket[i][j] >= 2 and check[i][j] == 0:
                temp.append((i,j))
                basket[i][j] -= 2
    cloud = temp
result = 0
for i in range(n):
    for j in range(n):
        result += basket[i][j]
print(result)

 

 

_____________________________________________________________________________________________________

 

파이썬에 더 익숙해지기 위해 swift보다 파이썬으로 먼저 풀어보았다. 문법이 아주 조금씩 익혀지는듯