2021.03.28
문제설명
- NXN 크기의 시험관
- 바이러스는 1번부터 K번 중 하나
- 1초마다 상하좌우 방향으로 증식하며, 번호가 낮은 바이러스 먼저 증식.
- 증식하려는 곳에 이미 바이러스가 있으면 증식 안함.
- S초 뒤에 주어진 좌표에 바이러스 종류를 찾는 문제
solution
- 바이러스 목록을 만듭니다. (맵을 돌며 바이러스가 있다면 해당 번호 목록에 넣음)
- S초 동안 바이러스가 퍼집니다.
- 네 방향을 돌며 바이러스가 퍼집니다.
- 이미 바이러스가 있다면 퍼지지 않습니다.
- 퍼진 바이러스는 기존 바이러스 목록에 포함시킵니다. (for loop에 영향받지 않도록 새로운 목록에 담아서 나중에 추가하는 방식으로 구현)
- 네 방향을 돌며 바이러스가 퍼집니다.
- 주어진 좌표에 있는 바이러스 종류를 리턴합니다.
구현1.
30564KB, 1004ms
한번 퍼진 바이러스는 4방향을 모두 확인한 상태이므로 다시 볼 필요가 없습니다.
바이러스 목록을 리스트로 만들어 추가 제거하는 식으로 구현하였는데,
큐로 구현하면 BFS처럼 갔던 곳을 제거할 필요없이 자연스럽게 안보게 될 것이라 생각하였습니다.
=> 구현2
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
def solution(N, K, S, Y, X, inputMap):
virus = [[] for _ in range(K+1)]
# 1. 바이러스 리스트 만들기
for y in range(N):
for x in range(N):
if inputMap[y][x] != 0:
virus[inputMap[y][x]].append((y, x))
# 2. S초 동안 바이러스가 퍼진다
for s in range(S):
for virusNo in range(K+1):
if len(virus[virusNo]) == 0:
continue
newVirus = []
removeVirus = []
for currentVirus in virus[virusNo]:
cnt = 0
# 3. 네 방향을 돌며 바이러스가 퍼진다.
for d in range(4):
nextY, nextX = currentVirus[0] + dy[d], currentVirus[1] + dx[d]
if 0 <= nextY < N and 0 <= nextX < N:
if inputMap[nextY][nextX] == 0:
inputMap[nextY][nextX] = inputMap[currentVirus[0]][currentVirus[1]]
newVirus.append((nextY, nextX))
else:
cnt += 1
else:
cnt += 1
if cnt == 4:
removeVirus.append(currentVirus)
virus[virusNo] += newVirus
# 3. 이미 다 퍼진 바이러스는 그룹에서 제거한다.
for r in removeVirus:
virus[virusNo].remove(r)
return inputMap[Y-1][X-1]
N, K = map(int, input().split())
inputMap = []
for n in range(N):
inputMap.append(list(map(int, input().split())))
S, Y, X = map(int, input().split())
print(solution(N, K, S, Y, X, inputMap))구현2
Queue를 이용해서 구현했더니 시간초과가 났습니다.
Python Queue가 효율이 떨어져서 Deque로 구현했습니다.
=> 구현3
from queue import Queue
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
def solution(N, K, S, Y, X, inputMap):
virus = [Queue() for _ in range(K+1)]
# 1. 바이러스 리스트 만들기
for y in range(N):
for x in range(N):
if inputMap[y][x] != 0:
virus[inputMap[y][x]].put((y, x))
# 2. S초 동안 바이러스가 퍼진다
for s in range(S):
for virusNo in range(K+1):
if virus[virusNo].qsize() == 0:
continue
for _ in range(virus[virusNo].qsize()):
currentVirus = virus[virusNo].get()
# 3. 네 방향을 돌며 바이러스가 퍼진다.
for d in range(4):
nextY, nextX = currentVirus[0] + dy[d], currentVirus[1] + dx[d]
if 0 <= nextY < N and 0 <= nextX < N:
if inputMap[nextY][nextX] == 0:
inputMap[nextY][nextX] = inputMap[currentVirus[0]][currentVirus[1]]
newVirus.put((nextY, nextX))
return inputMap[Y-1][X-1]
N, K = map(int, input().split())
inputMap = []
for n in range(N):
inputMap.append(list(map(int, input().split())))
S, Y, X = map(int, input().split())
print(solution(N, K, S, Y, X, inputMap))구현3
Deque로 구현하니 시간초과는 나지 않았는데 구현1보다 느렸습니다.
32856KB, 1756ms
시간복잡도 계산상으로는 빨라야할 것 같은데 왜그런지 모르겠습니다. 아시는분은 댓글로 알려주세요.
from collections import deque
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
def solution(N, K, S, Y, X, inputMap):
virus = [deque() for _ in range(K+1)]
# 1. 바이러스 리스트 만들기
for y in range(N):
for x in range(N):
if inputMap[y][x] != 0:
virus[inputMap[y][x]].append((y, x))
# 2. S초 동안 바이러스가 퍼진다
for s in range(S):
for virusNo in range(K+1):
for _ in range(len(virus[virusNo])):
currentVirus = virus[virusNo].popleft()
# 3. 네 방향을 돌며 바이러스가 퍼진다.
for d in range(4):
nextY, nextX = currentVirus[0] + dy[d], currentVirus[1] + dx[d]
if 0 <= nextY < N and 0 <= nextX < N:
if inputMap[nextY][nextX] == 0:
inputMap[nextY][nextX] = inputMap[currentVirus[0]][currentVirus[1]]
virus[virusNo].append((nextY, nextX))
return inputMap[Y-1][X-1]
N, K = map(int, input().split())
inputMap = []
for n in range(N):
inputMap.append(list(map(int, input().split())))
S, Y, X = map(int, input().split())
print(solution(N, K, S, Y, X, inputMap))
Comment