전염병 (python)

👀 깃헙 소스

BFS 문제풀이, 새롭게 감염된 사람과 이전에 감염된 사람이 섞이지 않게 temp 배열로 처리를 해야한다.

문제설명

m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다.

예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다.
사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요.

입출력 예

m	n	infests			vaccinateds		result
2	4	[[1,4],[2,2]]		[[1,2]]			2
2	3	[[2,2]]			[[1,2],[2,1],[2,3]]	-1
2	2	[[1, 1], [2, 2]]	[[1, 2], [2, 1]]	0

솔루션

감염자가 있다면 day를 하나 올려주고
현재 감염된 사람들의 상하좌우를 탐색하며 감염시키는 것이 가능한 자리를 찾는다. 이를 new_infests에 넣어준다. 새로 감염시킬 수 있는 사람들이 없어질때까지 반복문을 반복한다.

빈 구멍이 있다면 -1을 return 하고 아니면 날짜를 return 해준다.

코드

# 파이썬
def can_infest(y, x, m, n, state):
    return 0 <= y < m and 0 <= x < n and state[y][x] == 0

def solution(m, n, infests, vaccinateds):   
    blank = m*n - len(infests) - len(vaccinateds)
    if blank == 0: # 모두 백신이나 감염
        return 0
    
    state = [[0] * n for i in range(m)] # 상태 확인 표
    for y, x in vaccinateds + infests:
        state[y-1][x-1] = 1
        
    day = -1
    cur_infests = [(y-1, x-1) for y, x in infests]
    
    DELTAS, Y, X = [(0, 1), (0, -1), (-1, 0), (1, 0)], 0, 1
    while cur_infests:
        day += 1
        new_infests = []
        for infest in cur_infests:
            for dy, dx in DELTAS:
                nxt = infest[Y] + dy, infest[X] + dx
                if can_infest(*nxt, m, n, state):
                    new_infests.append(nxt)
                    state[nxt[Y]][nxt[X]] = 1
                    blank -= 1
        cur_infests = new_infests

    return day if blank == 0 else -1

주의
편의를 위해 day를 처음에 -1로 설정해주고 반복문에서 1씩더해준다.