21610 - 마법사 상어와 비바라기

레벨 5 문제로 크게 어렵지 않은 문제였다... 시간초과만 아니라면!!!

진짜 문제푸는데 걸린시간보다 시간초과 해결하는데 걸린시간이 더 긴 것 같다. 

 

아래는 제일 처음 냈던 풀이 방식이다. 

# 비구름 : [N, 1], [N, 2], [N-1, 1], [N-1, 2]
# 구름의 이동 M번 명령
global makeCloud

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

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

ds = []
for _ in range(M):
    ds.append(list(map(int, input().split())))

makeCloud = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]]
#  ←, ↖, ↑, ↗, →, ↘, ↓, ↙
# direction = [[0,-1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1]]
dx = [0,-1,-1,-1,0,1,1,1]
dy = [-1,-1,0,1,1,1,0,-1]

# 구름의 이동 -> 구름이 있는 칸에 비가 1씩 내리고, 구름이 사라짐
def firstMove(graph, d, s):
    locAfterMove = []
    for x, y in makeCloud:
        nx = (x+dx[d-1]*s+N)%N
        ny = (y+dy[d-1]*s+N)%N

        graph[nx][ny] += 1
        locAfterMove.append([nx, ny])
    return graph, locAfterMove

def secondMove(graph, locAfterMove):
    copyGraph = [tmpGraph[:] for tmpGraph in graph]
    newMakeCloud = []
    for x in range(N):
        for y in range(N):
            if [x, y] in locAfterMove:
                for i in range(4):
                    nx = x + dx[(i*2)+1]
                    ny = y + dy[(i*2)+1]
                    if 0<=nx<N and 0<=ny<N and graph[nx][ny] > 0:
                        copyGraph[x][y] += 1

            elif graph[x][y] >= 2:
                copyGraph[x][y] -= 2
                newMakeCloud.append([x, y])

    return newMakeCloud, copyGraph

for d, s in ds:
    first = firstMove(graph, d, s)
    newGraph = first[0]; locAfterMove = first[1]

    second = secondMove(graph, locAfterMove)
    makeCloud = second[0]; graph = second[1]

result = 0
for i in range(N):
    result += sum(graph[i])

print(result)

처음에는 구름이 있는 자리를 if _ in _ 으로 탐색했는데,  이를 visited라는 2차원 배열로 변경해서 탐색을 하니

시간초과 문제가 해결되었다... 너무 어이없어 ㅠ.ㅠ

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

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

ds = []
for _ in range(M):
    ds.append(list(map(int, input().split())))

makeCloud = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]]
dx = [0,-1,-1,-1,0,1,1,1]
dy = [-1,-1,0,1,1,1,0,-1]

def firstMove(graph, makeCloud):
    visited = [[False] * N for _ in range(N)]
    for x, y in makeCloud:
        nx = (x + dx[d - 1] * s + N) % N
        ny = (y + dy[d - 1] * s + N) % N

        graph[nx][ny] += 1
        visited[nx][ny] = True

    return graph, visited

def secondMove(graph, visited):
    makeCloud = []
    copyGraph = [tmp[:] for tmp in graph]
    for x in range(N):
        for y in range(N):
            if visited[x][y] == True:
                for i in range(4):
                    nx = x + dx[(i * 2) + 1]
                    ny = y + dy[(i * 2) + 1]
                    if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] > 0:
                        copyGraph[x][y] += 1

            elif graph[x][y] >= 2:
                copyGraph[x][y] -= 2
                makeCloud.append([x, y])

    return makeCloud, copyGraph

for d, s in ds:
    f = firstMove(graph, makeCloud)
    graph = f[0]; visited = f[1]

    s = secondMove(graph, visited)
    makeCloud = s[0]; graph = s[1]

result = 0
for i in range(N):
    result += sum(graph[i])

print(result)