[백준] 18405번 - 경쟁적 감염

1차

아이디어

move배열로 상,하,좌,우 방향으로 이동하며 값이 0일 경우 바이러스를 전염시킨다.

코드

N, K = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(N)]
S,X,Y = map(int,input().split())
move = [[-1,0],[1,0],[0,-1],[0,1]]
virus = [[(i,j)] for i in range(N) for j in range(N) for k in range(1,K+1) if lst[i][j] == k]

print(virus)
if S != 0:
    for s in range(S):
        for i in range(K):
            tmp = []
            for v in virus[i]:
                for m in move:
                    check1 = v[0] + m[0]
                    check2 = v[1] + m[1]
                    if (0 <= check1 < N) and (0 <= check2 < N) and (lst[check1][check2] == 0):
                            lst[check1][check2] = i + 1
                            tmp.append((check1, check2))
            virus[i] = tmp

print(lst)
print(virus)
print(lst[X-1][Y-1])

최종

아이디어

list로는 시간초과가 뜨기 때문에 deque를 통해 해결한다.
이때, 1번부터 K번까지 순서대로 바이러스를 전염시켜야 하기 때문에 deque를 오름차순 정렬해줘야 한다.

코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
lst = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
S,X,Y = map(int,input().split())

move = [[-1,0],[1,0],[0,-1],[0,1]]
virus = [[lst[i][j],i,j,0] for i in range(N) for j in range(N) if lst[i][j] != 0]

virus.sort() #lst[i][j] - 바이러스 값을 오름차순 정렬
virus = deque(virus)

while virus:
    v,i,j,t = virus.popleft() #바이러스 1번부터 값을 넣어두기
    if t == S:
        break
    else:
        for m in move:
            check1 = i + m[0]
            check2 = j + m[1]
            if (0 <= check1 < N) and (0 <= check2 < N) and (lst[check1][check2] == 0):
                lst[check1][check2] = v
                virus.append([v,check1,check2,t+1])
print(lst[X-1][Y-1])

시간단축

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
lst = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
S,X,Y = map(int,input().split())

move = [[-1,0],[1,0],[0,-1],[0,1]]
virus = [[lst[i][j],i,j,0] for i in range(N) for j in range(N) if lst[i][j] != 0]
virus.sort()

def virus_check(virus):
    queue = deque(virus)
    while queue:
        v, i, j, t = queue.popleft()
        if t == S:
            break
        else:
            for m in move:
                check1 = i + m[0]
                check2 = j + m[1]
                if (0 <= check1 < N) and (0 <= check2 < N) and (lst[check1][check2] == 0):
                    lst[check1][check2] = v
                    queue.append([v, check1, check2, t + 1])
    print(lst[X - 1][Y - 1])

virus_check(virus)

확실히 함수를 사용하니 시간 단축이 되었다.