[이코테] DFS/BFS_경쟁적 전염 (python)

문제

나의 풀이

1. 답은 맞지만.. 백준 시간 초과

import sys
input = sys.stdin.readline

n, k = map(int, input().split()) # n: 행렬의 크기, k: 바이러스의 수
arr = [] # 시험관의 정보를 담을 list
dfs = [[0] for _ in range(k + 1)] # 바이러스의 위치를 담을 list
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j]:
            dfs[arr[i][j]].append((i, j))
            
s, x, y = map(int, input().split()) # s: s초 뒤에 (x, y)에 존재하는 바이러스는?
go = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
dfs_cv = [x[:] for x in dfs]
for time in range(s): # s초 까지
    for virus in range(1, k + 1): # 바이러스는 k개 이내에
        for i, j in dfs[virus][1:]: # 해당 바이러스가 위치한 곳 전부를 살피며
            for g in go: # 상하좌우를 살펴서
                if 0 <= i + g[0] < n and 0 <= j + g[1] < n: # 시험관 안에서
                    if not arr[i + g[0]][j + g[1]]: # 바이러스가 없다면
                        arr[i + g[0]][j + g[1]] = arr[i][j]
                        dfs_cv[arr[i][j]].append((i + g[0], j + g[1]))
    dfs = dfs_cv # 시험관 정보 업데이트
print(arr[x - 1][y - 1])

: 애초에 4중 for문이라 시간 초과 날 것 같았음..
아 이거 왜케 생각이 안 떠오르냐

2.

from collections import deque
graph = []
virus = []
n, k = map(int, input().split()) # 크기, 바이러스 종류
for x in range(n):
    graph.append(list(map(int, input().split())))
    for y in range(n):
        if graph[x][y] != 0: # 바이러스가 있을 경우
            virus.append((graph[x][y], 0, x, y)) # 바이러스 종류, 시간, 위치(x, y)를 우선순위 큐에 삽입
virus.sort()
virus = deque(virus)
s, s_x, s_y = map(int, input().split())
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우

while virus:
    v, time, x, y = virus.popleft() # 바이러스 확산 시작
    if time == s:
        break
    for a, b in dir: # 상하좌우를 살피며
        next_x, next_y = x + a, y + b # 이동할 좌표
        if 0 <= next_x < n and 0 <= next_y < n: #시험관 범위 이내라면
            if graph[next_x][next_y] == 0: # 바이러스가 없다면
                graph[next_x][next_y] = v # 바이러스 확산
                virus.append((graph[next_x][next_y], time + 1, next_x, next_y))
print(graph[s_x - 1][s_y - 1]) # s_x, s_y 초 직전에 어떤 바이러스 였는지 반환

• 우선순위 q로 하면, 바이러스 종류가 빠른 것부터 다 해치우고 진행되기 때문에 그냥 덱으로 하기!

다른 사람 풀이

1. 숏코딩(백준)

import sys
input = sys.stdin.readline
n, k = map(int, input().split())

board = []
for _ in range(n):
    board.append([*map(int, input().split())])
    
s, x, y = map(int, input().split())
dist = [401] * (k+1)


for i in range(n):
    for j in range(n):
        d = abs(x-i-1) + abs(y-j-1)
        if d <= s and board[i][j] > 0:
            dist[board[i][j]] = min(dist[board[i][j]], d)

print(dist.index(min(dist)))