[week03] 백준 18405번 python 풀이

문제

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

18405번: 경쟁적 전염

왜 틀렸을까?

시간초과로 엄청 고생했던 문제였다.

 

시간초과를 줄여보기 위해서 

1. 바이러스가 우리가 구하고자 하는 좌표칸 안에 증식되게 되면 변하지 않는 점을 이용해서 우리가 구하고자 하는 위치에 바이러스가 증식되는 순간 종료시키는 코드를 추가했다.
2. 처음 짰던 코드에서는 바이러스의 종류별로(1~K 까지) 모두 확인하면서 코드를 짰었는데, 그 시간을 줄이기 위해서 전체 시험관을 한 번 돌때, 바이러스의 종류와 위치를 queue에 저장하고 더 이상 for문을 돌지 않는 식으로 코드 구조를 바꿨다.
3. 계속 수정을 해도 시간초과가 뜨길래, 시간초를 3초까지 줄여봤는데도 시간초과가 떴다. 

사실, 중요한건 전체 코드의 구조였다. 구조가 태생적으로 시간초과가 나는 코드였기 때문에 아무리 조금씩 시간을 줄여보아도 해결되지 않는 문제였다. 

 

틀렸던 코드에서는 바이러스 순서대로 queue에 삽입하기 위해서 1~K까지, N*N의 모든 칸을 순회했기 때문에 최악의 경우, 1000 * 200 * 200 = O(40000000)이 걸린다.

 

또한 queue에서 하나씩 pop할 때마다 1초가 증가하도록 코드를 짰는데, 그렇게 할 경우 같은 바이러스가 다른 여러 칸에 있을 때 문제에서 요구하는 방식대로 증식하지 못했다.

 

결론적으로 코드가 틀렸기 때문에 시간초과가 났던 것이었다. 결국 새로운 방식으로 문제를 해결했다.

중요 포인트

일단 K를 번호 낮은 순서대로 실행시키기 위해서 4천만번의 연산을 하는 대신, 우선순위 큐를 사용해서 4만번의 연산으로 바이러스의 우선순위를 해결했다.

 

이전 코드에서는 빈 칸을 만날 때마다 queue에 바이러스 번호와 위치를 넣어주었는데, 그렇게 하지 않고 모두 next_virus라는 배열에 값을 저장해놓았다가 1초가 지나는 시점에 한번에 queue에 삽입해주는 방식으로 초당 증식하는 바이러스를 구현했다.

 

BFS를 조금 응용한 문제였는데 조금만 응용해도 풀기가 어려웠다...

코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())  # n은 크기, k는 바이러스종류

board = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

S, X, Y = map(int, sys.stdin.readline().split())  # S초 뒤에 X,Y에 있는 바이러스
visited = [[False]*(N) for i in range(N)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

time = 0
virus = []
heap = []

for x in range(N):
    for y in range(N):
        if board[x][y] != 0:
            num = board[x][y]
            heapq.heappush(heap, (num, x, y))
            visited[x][y] = True

for _ in range(S):
    next_virus = []
    while heap:
        now = heapq.heappop(heap) # 우선순위큐로 바이러스에 우선순위 부여
        k, x, y = now[0], now[1], now[2]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] == 0:
                    board[nx][ny] = k
                    next_virus.append((k, nx, ny))
    for vir in next_virus: 
        heapq.heappush(heap, vir)     # 한번에 모두 삽입  

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