24513 좀비 바이러스

🥇 24513 좀비 바이러스

문제

---

여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$번, $2$번, $3$번으로 번호를 매겼다.

바이러스의 특징은 다음과 같다.

 - $1$번과 $2$번 바이러스는 치사율은 낮지만 전염성이 강해 상하좌우에 인접해 있는 마을로 동시에 퍼져나가며 한 마을을 완전히 감염시키는 데 1시간 걸린다.

• 마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다.
• 마을이 한 바이러스에 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 $3$번 바이러스가 만들어진다.
•  $3$번 바이러스는 치사율이 높은 만큼 전염성이 약해 감염된 마을에서 더 이상 퍼지지 않는다.
• 치료제를 갖고 있는 마을은 감염시킬 수 없다.

 $1$번 바이러스와 $2$번 바이러스에 감염된 마을이 나와버렸다. 바이러스가 퍼질 수 있는 대로 퍼졌을 때 $1$번, $2$번, $3$번 바이러스에 감염된 마을이 각각 몇 개일지 구해보자.

입력

---

첫째 줄에 $N$($2≤N≤1\,000$)과 $M$($2≤M≤1\,000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 마을의 상태가 $M$개 주어진다. 마을의 상태는 다음과 같이 이루어져 있다.

•  $-1$: 치료제를 가진 마을
•  $0$: 아직 감염되지 않은 마을
•  $1$: $1$번 바이러스에 감염된 마을
•  $2$: $2$번 바이러스에 감염된 마을

 $1$번 바이러스와 $2$번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

출력

---

 $1$번, $2$번, $3$번 바이러스에 감염된 마을의 수를 공백으로 구분하여 한 줄에 출력한다.

분석

---

pypy로 메모리, 시간 겨우겨우 통과했다..ㅎㅎ 나중에 시간나면 다시 풀어봐야 될 문제 ㅠㅠ
문제 자체는 어렵지 않은데 구현해내는데 좀 시간이 걸린 것같다. 말 그대로 1번 바이러스와 2번 바이러스가 겹치는 곳에 3번 바이러스가 생긴다. 나는 이걸 visited 배열을 만들어 [먼저 와있는 바이러스, 걸린 시간]으로 저장해서 비교해 주었다.
그동안 bfs로는 하나의 대상(바이러스)가 퍼트려지는 문제들이였는데, 이 문제는 2개의 바이러스가 동시에 퍼지는 것이고 추가된 조건, 바이러스 3이 생겨난다는게 쉽지 않았다...

소스 코드

---

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())

board = []
virus = [[],[0, 0], [0, 0]]
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 1:
            virus[1] = [i, j]
        elif tmp[j] == 2:
            virus[2] = [i, j]
    board.append(tmp)

def check(x, y):
    if 0 <= x < N and 0 <= y < M:
        return True
    else:
        return False

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque([[virus[1][0], virus[1][1], virus[2][0], virus[2][1]]])

visited = [[[0, -1] for _ in range(M)] for _ in range(N)]
visited[virus[1][0]][virus[1][1]][0] = 1
visited[virus[1][0]][virus[1][1]][1] = 0
visited[virus[2][0]][virus[2][1]][0] = 2
visited[virus[2][0]][virus[2][1]][1] = 0

while q:
    v1x, v1y, v2x, v2y = q.popleft()

    for i in range(4):
        v1nx, v1ny = v1x + dx[i], v1y + dy[i]
        v2nx, v2ny = v2x + dx[i], v2y + dy[i]

        flag1 = check(v1nx, v1ny)
        flag2 = check(v2nx, v2ny)
        add = [-1, -1, -1, -1]
        if flag1 and visited[v1nx][v1ny][1] == -1 and board[v1x][v1y] == 1 and board[v1nx][v1ny] == 0:
            add[0], add[1] = v1nx, v1ny
            board[v1nx][v1ny] = 1
            visited[v1nx][v1ny] = [1, visited[v1x][v1y][1] + 1]

        elif flag1 and visited[v1nx][v1ny][0] != 1 and visited[v1nx][v1ny][1] == visited[v1x][v1y][1] + 1:
            board[v1nx][v1ny] = 3

        if flag2 and visited[v2nx][v2ny][1] == -1 and board[v2x][v2y] == 2 and board[v2nx][v2ny] == 0:
            add[2], add[3] = v2nx, v2ny
            board[v2nx][v2ny] = 2
            visited[v2nx][v2ny] = [2, visited[v2x][v2y][1] + 1]
        elif flag2 and visited[v2nx][v2ny][0] != 2 and visited[v2nx][v2ny][1] == visited[v2x][v2y][1] + 1:
            board[v2nx][v2ny] = 3

        if sum(add) != -4:
            q.append(add)

c1 = c2 = c3 = 0
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            c1 += 1
        elif board[i][j] == 2:
            c2 += 1
        elif board[i][j] == 3:
            c3 += 1

print(c1, c2, c3)

소스 코드

---

시간을 5배나 줄인 코드이다. 전에 시도했던 코드에서 몇 부분만 바꾸어주었더니 통과 되었다. 중간에 10은 그냥 아무 값이나 넣고 나중에 확인을 위한 용도로 저장한 것이다.

import sys
from collections import deque
input = sys.stdin.readline

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

virus1 = []
virus2 = []
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            virus1 = [i, j]
        elif board[i][j] == 2:
            virus2 = [i, j]

q1 = deque([(virus1[0], virus1[1])])
q2 = deque([(virus2[0], virus2[1])])

q3 = deque()
while q1 or q2:

    # -- 바이러스 1 --
    len_q1 = len(q1)
    for k in range(len_q1):
        v1_x, v1_y = q1.popleft()

        if board[v1_x][v1_y] == 1:
            for nx, ny in (v1_x - 1, v1_y), (v1_x + 1, v1_y), (v1_x, v1_y + 1), (v1_x, v1_y - 1):
                if nx < 0 or ny < 0 or nx >= N or ny >= M:
                    continue
                if board[nx][ny] == 0:
                    q3.append((nx, ny))
                    board[nx][ny] = 10

    # -- 바이러스 2 --
    len_q2 = len(q2)
    for k in range(len_q2):
        v2_x, v2_y = q2.popleft()

        if board[v2_x][v2_y] == 2:
            for nx, ny in (v2_x - 1, v2_y), (v2_x + 1, v2_y), (v2_x, v2_y + 1), (v2_x, v2_y - 1):
                if nx < 0 or ny < 0 or nx >= N or ny >= M:
                    continue

                if board[nx][ny] == 0:
                    q2.append((nx, ny))
                    board[nx][ny] = 2

                elif board[nx][ny] == 10:
                    board[nx][ny] = 3
    while q3:
        v3_x, v3_y = q3.popleft()
        if board[v3_x][v3_y] == 10:
            board[v3_x][v3_y] = 1
            q1.append((v3_x,v3_y))

cnt_1 = cnt_2 = cnt_3 = 0
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            cnt_1 += 1
        if board[i][j] == 2:
            cnt_2 += 1
        if board[i][j] == 3:
            cnt_3 += 1
print(cnt_1, cnt_2, cnt_3)