[10/17] 18405 (경쟁적 전염)

실버1 문제
DFS/BFS 실패

내 코드 (구현은 했지만 시간초과)

from collections import deque
import sys

n, k = map(int, input().split())
arr = []

move_h = [1, -1, 0, 0]
move_w = [0, 0, 1, -1]

for _ in range(n):
    arr.append(list(map(int, input().split())))
    
s, x, y = map(int, input().split())
newmap = [item[:] for item in arr]   #새로운 리스트
distance = [[300] * n for _ in range(n)] #최단거리 리스트

# 시간제한 고려
def bfs(h, w):
    level = arr[h][w]
    queue = deque()
    queue.append([h, w])
    
    while queue:
        hh, ww = queue.popleft()
        for i in range(4):
            temp_h = hh + move_h[i]
            temp_w = ww + move_w[i]
            
            mini = abs(h - temp_h) + abs(w - temp_w)
            # s초 지났는지 확인 
            if ( mini > s ):
                break
            
            # 지도 밖으로 나갔는지 확인
            if ( temp_h < 0 or temp_h >= n or temp_w < 0 or temp_w >= n ):
                continue
            
            # 원래 arr에 바이러스가 있는지 확인
            if arr[temp_h][temp_w] != 0:
                continue
                
            # 이미 증식했던 곳인지 확인
            if ( newmap[temp_h][temp_w] == level ):
                continue
                
            # 최단거리보다 클 경우
            if ( mini > distance[temp_h][temp_w] ):
                continue
            # 최단거리와 같을 경우
            elif (mini == distance[temp_h][temp_w]):
                #레벨 비교
                if ( level >= newmap[temp_h][temp_w] ):
                    continue
                
            newmap[temp_h][temp_w] = level
            distance[temp_h][temp_w] = mini   # 최단거리 지정
            queue.append([temp_h, temp_w])
    
for i in range(n):
    for j in range(n):
        if ( arr[i][j] != 0 ):
            bfs(i, j)
            
print(newmap[x-1][y-1])

효율적인 코드

from collections import deque

n, k = map(int, input().split())
arr = []
data = []

for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j] != 0:
            data.append((arr[i][j], 0, i, j))
            
data.sort()
queue = deque(data)

target_s, target_h, target_w = map(int, input().split())

move_h = [1, -1, 0, 0]
move_w = [0, 0, 1, -1]

while queue:
    level, s, h, w = queue.popleft()
    
    if s == target_s:
        break
        
    for i in range(4):
        temp_h = h + move_h[i]
        temp_w = w + move_w[i]
        
        if ( 0 <= temp_h < n and 0 <= temp_w < n ):
            if arr[temp_h][temp_w] == 0:
                arr[temp_h][temp_w] = level
                queue.append((level, s+1, temp_h, temp_w))
                
print(arr[target_h - 1][target_w - 1])

로직

• 처음부터 차례대로 탐색하면 시간초과가 뜬다.
• level이 낮은 바이러스부터 차례대로 BFS를 해야한다. (queue 자료구조이기 때문에 시간에 따라 증식한다.)

피드백

• 리스트 얕은 복사...