백준 #24513 좀비 바이러스

코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline
from collections import deque

def solve():
    while q:
        r, c, v, time = q.popleft()
        if visited[r][c][0] == 3:
            continue
        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if nr < 0 or nr >= n or nc < 0 or nc >= m:
                continue
            if visited[nr][nc][0] == 3:                 #   치료제 or 3번 바이러스 있는 곳은 침투 불가능
                continue
            if visited[nr][nc][0] == 0:                 #   아직 감염 안된 곳이면
                visited[nr][nc][0] = v
                visited[nr][nc][1] = time + 1
                q.append((nr, nc, v, time + 1))
                arr[nr][nc] = v
            else:
                if visited[nr][nc][1] == time + 1 and visited[nr][nc][0] != v:
                    visited[nr][nc][0] = 3
                    arr[nr][nc] = 3
    return


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

visited = [[[0, 0] for _ in range(m)] for _ in range(n)]    # 감염된 바이러스 종류, 시간
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
q = deque()

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q.append((i, j, 1, 0))
            visited[i][j][0] = 1
            visited[i][j][1] = 0
        elif arr[i][j] == 2:
            q.append((i, j, 2, 0))
            visited[i][j][0] = 2
            visited[i][j][1] = 0
        if arr[i][j] == -1:
            visited[i][j][0] = 3

solve()

cnt1 = cnt2 = cnt3 = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            cnt1 += 1
        elif arr[i][j] == 2:
            cnt2 += 1
        elif arr[i][j] == 3:
            cnt3 += 1

print(cnt1, cnt2, cnt3)

풀이

후…2시간30분만에 푼 문제다. 예제조차 통과하지 못해서 너무 힘들었었다.

풀릴 듯 말 듯 나를 괴롭혀서 많이 화났었다…!!!!

포인트는 좌표가 큐에 들어있는동안 3으로 감염될 수 있다는 것이다.

따라서 pop을 해주고 3이 아닌 경우에만 bfs를 다시 돌아주면 된다!!!!

감염 탈출!!