백준 / 경쟁적 전염 / 18405번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 경쟁적 전염 / 18405번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/18405

 

문제 설명

---

나의 풀이

from collections import deque


def solution(virus_map, s, target_x, target_y, n):
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    # 초기 바이러스 위치 수집 및 정렬
    initial = []
    for y in range(n):
        for x in range(n):
            if virus_map[y][x] != 0:
                initial.append((virus_map[y][x], 0, y, x))  # (virus 번호, 시간, y, x)

    # 바이러스 번호 오름차순으로 정렬 후 큐에 넣기
    dq = deque(sorted(initial))

    while dq:
        virus_type, time, y, x = dq.popleft()

        if time == s:
            break

        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < n and virus_map[ny][nx] == 0:
                virus_map[ny][nx] = virus_type
                dq.append((virus_type, time + 1, ny, nx))

    return virus_map[target_y - 1][target_x - 1]


def main():
    n, k = map(int, input().split())

    virus = [list(map(int, input().split())) for _ in range(n)]

    s, y, x = map(int, input().split())

    print(solution(virus, s, x, y, n))


if __name__=="__main__":
    main()

---

※ 알아야 할 것

아래의 코드는 시간 초과한 코드입니다. 매 초마다 모든 바이러스를 탐지해서 다시 뿌리는 작업은 시간복잡도 측면에서 오래 걸리는 문제가 발생했습니다.

def solution(virus, s, rx, ry, n):
    # 상 하 좌 우 움직임
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    for seconds in range(1, s + 1):
        # 데크를 이용한 풀이
        dq = []

        for y in range(n):
            for x in range(n):
                if virus[y][x] != 0:
                    dq.append((virus[y][x], y, x))

        # 오름차순으로 정렬
        dq = deque(sorted(dq, key=lambda m: m[0]))

        # 바이러스 퍼지는 상태 표기
        while dq:
            num, ny, nx = dq.popleft()

            for iy, ix in move:
                y = iy + ny
                x = ix + nx
                if 0 <= y < n and 0 <= x < n and virus[y][x] == 0:
                    virus[y][x] = num

    return virus[ry - 1][rx - 1]