> 문제 <

https://www.acmicpc.net/problem/18405

> 풀이 <

> 코드 <

# 경쟁적 전염

n, k = map(int, input().split())
space = []
for _ in range(n):
    space.append(list(map(int, input().split())))
s, x, y = map(int, input().split())
d = [(1, 0),(-1, 0), (0, 1), (0, -1)]
visited = [[0] * n for _ in range(n)]


def bfs(x, y):                           # 바이러스 전염
    visited[x][y] = 1
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        if 0 <= nx < n and 0 <= ny < n and space[nx][ny] == 0 and not visited[nx][ny]:
            visited[nx][ny] = 1
            space[nx][ny] = space[x][y]


virus = []
virus_visited = [[0] * n for _ in range(n)]
count = 0                        # 시간 (초)
while count < s:
    if all(0 not in l for l in space):              # 0이 하나도 존재하지 않는지 = 바이러스 all 전염 (s 무쓸모)
        break
    for i in range(n):
        for j in range(n):
            if space[i][j] != 0 and not virus_visited[i][j]:
                virus_visited[i][j] = 1             # 탐색 완료
                virus.append([i, j])

    virus.sort(key = lambda x: space[x[0]][x[1]])   # 바이러스 숫자가 작은 순서대로 정렬 - x[0], x[1] 행 열 (x = 1차원 배열 원소)
    for arr in virus:
        bfs(arr[0], arr[1])
    count += 1

print(space[x-1][y-1])

# someone's code

from collections import deque

n, k = map(int, input().split())
space, virus = [], []
for xx in range(n):
    temp = list(map(int, input().split()))
    space.append(temp)
    for yy, value in enumerate(temp):
        if value != 0:
            virus.append((value, 0, xx, yy))           # 바이러스 넘버, 시간(초), 좌표값 x, y

queue = deque(sorted(virus))                        # 바이러스 넘버순으로 정렬

s, X, Y = map(int, input().split())
d = [(1, 0),(-1, 0), (0, 1), (0, -1)]

while queue:
    v, cnt, x, y = queue.popleft()
    if cnt == s:
        break
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        if 0 <= nx < n and 0 <= ny < n and space[nx][ny] == 0:
            space[nx][ny] = v
            queue.append((v, cnt + 1, nx, ny))

print(space[X-1][Y-1])

나의 코드와 다른 사람의 코드를 비교해봤을 때, 메모리 사용은 비슷하지만 시간 차이가 꽤 컸다.
다른 코드가 queue 이용 + 영리하게 풀어서 시간 차이가 나는 것 같다!

queue에 여러 가지 원소를 담고 뽑아쓸 수 있는 것을 기억하자!
첫 바이러스 상태 space에 관한 필요 원소들을 virus에 넣고 그 2차원 virus 리스트를 queue에 초기에 넣어준 채로 시작한다. queue = deque(sorted(virus))

while queue: 뒷 부분에
새롭게 queue.append((v, cnt+1, nx, ny)) 를 해주어 queue 맨 뒤에 들어갈 수 있게 해준다.
윗 줄 조건식 때문에 space에 0이 없어지게 되면( 모두 전염되면 ) queue에 삽입이 진행되지 않으므로 while문 탈출!
----> 내가 길게 썼던 부분들 (virus 원소값대로 정렬 (난 좌표값만 넣어놔서 lamda를 사용했던건데...) , space에 더이상 0이 존재하지 않는다면 ) 등등을 간단하게 엮어서 구현한 것을 확인할 수 있다.