글 읽기 - 17144번 미세먼지 안녕!

skk095 4년 전 0

testcase에 나온 것들 모두 통과 되었고, 알고리즘 자체도 맞는 것 같은데

시간 초과가 납니다ㅠ 시간 초과 해결하려면 어떻게 해야할까요....?

python 코드입니다.

from collections import deque
r, c, t = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(r)]
nmap = [[0] * c for _ in range(r)]

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

up = [[0, 1], [-1, 0], [0, -1], [1, 0]]
down = [[0, 1], [1, 0], [0, -1], [-1, 0]]
machine = []

for i in range(t):
    #미세먼지 확산 시키기
    q = deque()
    for x in range(r):
        for y in range(c):
            if a[x][y] != -1 and a[x][y] != 0:
                q.append([x,y])
            if a[x][y] == -1:
                machine.append([x, y])

    while q:
        x,y = q.popleft()
        tt = 0
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < r and 0 <= ny < c and a[nx][ny] != -1:
                nmap[nx][ny] += a[x][y] // 5
                tt += 1
        nmap[x][y] = nmap[x][y] + (a[x][y] - a[x][y] // 5 * tt)

    #위에 있는 공기청정기 시계 반대 방향으로 청정 시작
    sx, sy = machine[0][0], machine[0][1]
    x, y = sx, sy + 1
    u = 0
    tmp = nmap[x][y]
    nmap[x][y] = 0
    while (x != sx or y != sy):
        nx, ny = x + up[u][0], y + up[u][1]
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            u += 1
            continue
        else:
            tmp2 = nmap[nx][ny]
            nmap[nx][ny] = tmp
            tmp = tmp2
            x, y = nx, ny

    nmap[sx][sy] = 0

    #아래에 있는 공기 청정기 시계 방향으로 청정 시작
    sx, sy = machine[1][0], machine[1][1]
    x, y = sx, sy + 1
    u = 0
    tmp = nmap[x][y]
    nmap[x][y] = 0
    while (x != sx or y != sy):
        nx, ny = x + down[u][0], y + down[u][1]
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            u += 1
            continue
        else:
            tmp2 = nmap[nx][ny]
            nmap[nx][ny] = tmp
            tmp = tmp2
            x, y = nx, ny
    nmap[sx][sy] = 0

    a = nmap
    nmap = [[0] * c for _ in range(r)]

total = 0
for ss in range(r):
    for pp in range(c):
        total+=a[ss][pp]
print(total)

jhlim 4년 전 1

pypy3에서 시간초과 없이 맞았습니다 나옵니다. 제출해보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17144번 미세먼지 안녕!

skk095 4년 전 0

jhlim 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말