[백준] 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)
확실히 함수를 사용하니 시간 단축이 되었다.
Author And Source
이 문제에 관하여([백준] 18405번 - 경쟁적 감염), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yerimstar/백준-18405번-경쟁적-감염저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)