[python] 프로그래머스 - 전염병

문제 설명

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

예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다.

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

제한 사항

• $ 1 <= m,n <= 300 $인 자연수 m,n
• infests의 길이는 1이상 m*n 이하
  • infests의 원소는 [a,b]의 형식으로 사무실 내 좌표값을 의미함. ($1\leq a \leq m, 1 \leq b \leq n$)
  • infests에는 같은 원소가 중복되지 않음
• vaccinateds의 길이는 1이상 m*n이하로, infests와 동일한 형식
• 백신을 맞은 직원이 병에 걸린 경우는 주어지지 않음
• 병을 아무리 퍼뜨려도 백신을 맞은 직원을 제외한 모든 직원이 병에 감염될 수 없다면 -1을 리턴
  • 병에 걸린 직원 주위의 직원이 모두 백신 접종을 완료한 경우가 이 경우 중 하나

입출력 예

---

로직 및 풀이

로직

이 문제는 배열을 한 번만 탐색하면 되는 문제이고, 다만 탐색을 시작할 때 정점이 1개보다 많을 수 있다는 점에 유의한다. 또한 최종적으로 모든 직원이 병에 감염되기까지 며칠(탐색 시 level이 관건이 되는 것)이 걸리는지를 판단해야 하기 때문에, dfs보다는 bfs를 사용하는 것이 옳다.
전체 사무실을 별도의 배열로 구현할 수도 있고 하지 않을 수도 있지만, 하지 않는 경우엔 infests를 일종의 visited로 생각하고 append를 해줘야 한다. 이렇게 되면 방문을 확인할 때에 $O(n)$의 시간복잡도(엄밀히 말하면 아니지만)가 소요될 수 있기 때문에 전체 사무실을 배열로 구현해서 해당 직원의 감염 여부 혹은 백신 접종 여부를 보다 효율적으로 판단하도록 한다.
여기서 신경썼던 점은 며칠 째인지 어떻게 확인을 할지였다. 간단하게 그냥 현재 몇번째 level인지까지 큐에 삽입을 해주는 형태로 구현을 했다.
또한 모든 직원이 병에 감염될 수 없는 경우는 감염된 사람과 백신 접종이 완료된 사람의 숫자가 전체 숫자보다 작을 때이기 때문에 간단한 조건문으로 해결이 가능하다.

로직을 정리하면 다음과 같다.

1. mxn 2차원 영행렬을 만듦 (room 구현)
2. infests 인덱스에는 1, vaccinateds 인덱스에는 -1을 대입
3. Queue 초기화 (infests 초기 상태 삽입)
4. Queue에서 dequeue 후, 상하좌우로 인접정점 탐색하여 감염 가능 여부 확인 및 며칠차(bfs 레벨)인지 체크
5. 감염 가능한 경우 Queue에 삽입 후 Queue가 완전히 비워질 때까지 4를 수행
6. 탐색 종료된다면 며칠차인지 반환 후 프로그램 종료

코드

from collections import deque

def solution(m, n, infests, vaccinateds):
    """
    mxn 2차원 0 배열을 만듦.
    infests 자리에다가는 1 넣어주고,
    vaccinateds 자리에는 -1을 넣어주면 됨. 
    --> 배열 초기화 완료
    굳이 room 배열을 안만들고 infests랑 vaccinateds만으로도 충분히 구현은 가능할 것 같다.
    -> 그렇게 하면 조건 체크할 때 O(n)이라서 시간적으로 비효율적임.

    이 문제는 배열을 한 번만 탐색하면 되는 문제이므로, Queue를 하나 만들어서 차례로 infests 정점 삽입해주면 됨.
    """
    answer, count = 0, len(infests)

    room = [[0 for _ in range(n)] for _ in range(m)]

    for r,c in infests:
        room[r-1][c-1] = 1

    for r, c in vaccinateds:
        room[r-1][c-1] = -1

    Q = deque([[r-1,c-1,0] for r,c in infests])
    direction = [(-1,0), (1,0), (0,-1), (0,1)] # 상하좌우 direction 정의

    while Q:
        r,c,lv = Q.popleft()

        for dr, dc in direction:
            nr, nc = r+dr, c+dc

            if 0 <= nr < m and 0 <= nc < n and room[nr][nc] == 0:
                count += 1
                room[nr][nc] = 1
                Q.append([nr, nc, lv+1])

    # 모든 직원이 질병에 걸리지 않는 경우를 판단
    if count+len(vaccinateds) != m*n:
        return -1

    answer = lv
    return answer

기존에는 count 변수를 두지 않고 rooms를 -1이 디폴트인 2차원 행렬로 구현 후 vaccinateds 인덱스에 0을 대입하고 마지막에 summation 후 예외처리를 하는 방식(모든 직원이 질병에 감염되지 않는 경우에 대한 처리)으로 수행했다. 하지만 summation 시 실제 $O(n)$의 시간복잡도($n$: 2차원 행렬의 총 길이)가 소요되는 데다가 어차피 이전에 배열 내 질병에 감염되는 경우를 체크할 수 있으므로(while loop 내에서), count 변수를 두어 처리하는 방식으로 추후 수정했다.

---

정리

이번에도 1차 풀이에서 효율성 문제에서 문제가 생겼다. room을 구현하지 않고 바로 infests와 vaccinateds 내에 해당 원소가 존재하는지를 판단하는 식으로 조건문을 작성했기 때문이다. 이 경우에는 $O(n)$ ($n$: infests와 vaccinateds의 길이, 대략적인 표현)의 시간이 들기 때문에 비효율적이다. 이런 부분을 사전에 조금 더 생각하는 게 좋았을 것 같다. floodfill과 비슷한 문제로 생각을 했지만, floodfill은 모든 정점에 대해서 bfs를 수행해야하지만 이 문제에서는 bfs를 한 번 수행함으로써 문제가 쉽게 해결이 되었다. 또한 dfs 접근이 어려웠다는 점에서도 조금 달랐다. 이런 부분을 캐치해냈다는 점에서 스스로를 칭찬해주고 싶다.