[백준 문제풀이] 얼렁뚱땅 21610 마법사 상어와 비바라기 풀이

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

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

 

# 시간초과 : 하라는 대로 했지만 시간초과가 났다

- 알고보니까 [p,q] not in cloud 와 같이 있나 없나 Search 하는 과정이 오래 걸리는 거라고 한다.

import sys

n, m = map(int,sys.stdin.readline().strip().split())
arr = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)]
d = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(m)]

dx = (0, 0, -1, -1, -1, 0, 1, 1, 1)
dy = (0, -1, -1, 0, 1, 1, 1, 0, -1)


daegak_x = (1, 1, -1, -1)
daegak_y = (1, -1, 1, -1)


for i in range(m) :
    if i == 0 :
        cloud = [(n-1,0),(n-1,1), (n-2,0), (n-2,1)]
    
    # 구름이 이동한다. 그리고 구름이 있는 곳의 바구니에 저장된 물 1 증가
    for j in range(len(cloud)) :
        cloud[j][0] = (cloud[j][0] + d[i][1]*dx[d[i][0]]) % n
        cloud[j][1] = (cloud[j][1] + d[i][1]*dy[d[i][0]]) % n

        arr[cloud[j][0]][cloud[j][1]] += 1

    # cloud 있어서 물이 증가 된 것에 '물복사버그' 마법 시행
    # 대각선 거리 1인 칸에 물이 있는 '바구니 수'만큼 바구니 물 증가
    for j in range(len(cloud)) :
        count = 0
        for k in range(4) :
            nx = cloud[j][0] + daegak_x[k]
            ny = cloud[j][1] + daegak_y[k]
            if 0<=nx<n and 0<=ny<n :
                if arr[nx][ny] >= 1 :
                    count += 1
        arr[cloud[j][0]][cloud[j][1]] += count

    # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양 2가 줄어든다.
    # 이때, 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야한다.
    new_cloud = []
    for p in range(n) :
        for q in range(n) :
            if (arr[p][q] >= 2) and ([p,q] not in cloud) :
                new_cloud.append([p,q])
                arr[p][q] -= 2
    cloud = new_cloud

total = 0  
for i in range(n) :
    total += sum(arr[i])

print(total)

 

 

# 성공

- 그래서 visited[p][q] == 0 으로 바꾸어 줬땅

import sys
from collections import deque

n, m = map(int,sys.stdin.readline().strip().split())
arr = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)]
# d : [방향, 속력] # 전체 구름이가 얘가 움직이라는대로 움직여야 함
d = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(m)]
d = deque(d)

dx = (0, 0, -1, -1, -1, 0, 1, 1, 1)
dy = (0, -1, -1, 0, 1, 1, 1, 0, -1)


daegak_x = (1, 1, -1, -1)
daegak_y = (1, -1, 1, -1)

cloud = deque([(n-1,0),(n-1,1), (n-2,0), (n-2,1)])

while d :
    bang, sok = d.popleft()
    # 구름이 이동한다. 그리고 구름이 있는 곳의 바구니에 저장된 물 1 증가
    visited = [[0]*n for _ in range(n)]
    next_cloud = []
    while cloud :
        x, y= cloud.popleft()
        x = (x + sok * dx[bang]) % n
        y = (y + sok * dy[bang]) % n
        visited[x][y] = 1
        arr[x][y] += 1
        next_cloud.append([x,y])

    # cloud 있어서 물이 증가 된 것에 '물복사버그' 마법 시행
    # 대각선 거리 1인 칸에 물이 있는 '바구니 수'만큼 바구니 물 증가
    for j in range(len(next_cloud)) :
        count = 0
        x, y = next_cloud[j][0],next_cloud[j][1]
        for k in range(4) :
            nx = x+ daegak_x[k]
            ny = y + daegak_y[k]
            if 0<=nx<n and 0<=ny<n :
                if arr[nx][ny] >= 1 :
                    count += 1
        arr[x][y] += count

    # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양 2가 줄어든다.
    # 이때, 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야한다.

    for p in range(n) :
        for q in range(n) :
            if (arr[p][q] >= 2) and visited[p][q] == 0 :
                cloud.append([p,q])
                arr[p][q] -= 2

total = 0  
for i in range(n) :
    total += sum(arr[i])

print(total)