31791 : 바이러스 공격 Python

건물에 완전히 전파되기까지 시간이 걸려서 굉장히 까다로운 문제였다.
건물이 완전히 전파되기까지는 방문처리를 하면 안되고, 완전히 전파되면 인접 구역으로 전파된다는 점이 고민을 많이 하게했던 문제같다.

풀이 고민

처음에는 큐에 (전파까지 남은 시간, y좌표, x좌표)의 형태로 관리하려고 했다. 만약 건물이라면 Tb의 시간을 넣고 이후 큐에서 빼고 1씩 감소시킨 뒤 다시 넣어줬고, 건물이 아니라면 0의 시간을 넣었다. 그래서 남은 시간이 0인 경우에만 인접 좌표로 전파시키도록 했는데, 아마 넣었다 빼는 과정에서 시간 초과가 난 것 같다.

 

그 뒤에는 방문 처리를 3차원 배열을 통해서 수행해보려고 했다. 건물이 Tb의 시간 이후에는 모든 층에 퍼지게 되므로 Tb의 층을 가진다고 볼 수 있다.
이렇게 v[Tb][y좌표][x좌표]를 가지는 3차원 배열과 건물일 경우 Tb의 층을 방문하기 전까지는 전파시키지 않도록 했다. 역시 시간 초과가 났는데 결국 넣었다 빼는 과정이 문제가 맞는 것 같았다.

결국 따로 건물을 관리하는 building_q를 두고, 건물 방문 여부를 처리하는 set()을 따로 두어 해결했다.

풀이

핵심적인 부분은 건물을 관리하는 로직이다.

처음 건물에 전파되면 좌표를 방문처리하고 building_q에 (최초 전파된 시간, y좌표, x좌표)의 형태로 저장한다. 건물이 아닌 구역에 전파되면 즉시 큐에 삽입한다. 최초 전파된 시점부터 Tb의 시간이 흐르기 전까지는 인접 구역에 전파되지 않는다. 또한, building_q에는 최초 건물을 방문한 경우에만 저장되므로 항상 오름차순으로 정렬된다. 따라서, 현재 시간 - 최초 전파된 시간이 Tb보다 작다면 이 후 건물들은 볼 필요도 없이 전파되지 않는다.

 

완전히 전파된 건물들은 building_q에서 제거해주고, 해당 좌표에는 방문처리를 해주면 된다. 그리고 이제부터는 인접 구역으로 다시 전파가 가능하니 virus_q에도 넣어준다. 코드로 보면 아래와 같다.

def propagate(time):
    while building_q:
        if time - building_q[0][0] < durability:
            break
        t, y, x = building_q.popleft()
        visited[y][x] = True
        virus_q.append((y, x))

전체 코드

import sys
from collections import deque

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
# f = open("input.txt", "rt")
# input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
DIRECTIONS = (-1, 0), (1, 0), (0, -1), (0, 1)

N, M = map(int, input().split())
T, durability, X, B = map(int, input().split())

visited = [[False] * (M + 1) for _ in range(N + 1)]

_map = [[]]
virus_q = deque()
for i in range(1, N + 1):
    row = ["x"] + list(input().rstrip())
    for j in range(1, M + 1):
        if row[j] == "*":
            virus_q.append((i, j))
            visited[i][j] = True
    _map.append(row)
v_building = set()
building_q = deque()


def propagate(time):
    while building_q:
        if time - building_q[0][0] < durability:
            break
        t, y, x = building_q.popleft()
        visited[y][x] = True
        virus_q.append((y, x))


def BFS():
    time = 0
    while (virus_q or building_q) and time < T:
        time += 1
        q_size = len(virus_q)
        for _ in range(q_size):
            y, x = virus_q.popleft()

            for dy, dx in DIRECTIONS:
                ny, nx = dy + y, dx + x

                if (
                    ny > N
                    or nx > M
                    or ny < 1
                    or nx < 1
                    or visited[ny][nx]
                    or (ny, nx) in v_building
                ):
                    continue

                if _map[ny][nx] == "#":
                    v_building.add((ny, nx))
                    building_q.append((time, ny, nx))
                elif _map[ny][nx] == ".":
                    virus_q.append((ny, nx))
                    visited[ny][nx] = True
        propagate(time)


def main():
    BFS()
    ans = []
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if visited[i][j]:
                continue
            ans.append(f"{i} {j}")

    if not ans:
        print("-1")
        return
    print("\n".join(ans))


if __name__ == "__main__":
    main()