문제 링크 https://www.acmicpc.net/problem/24513
난이도 골드 3
문제 유형 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 파악

• 1번, 2번 바이러스는 상하좌우로 인접한 마을에 동시에 퍼져 나감
• 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 3번 바이러스가 만들짐
  • 3번 바이러스는 더 이상 퍼지지 않음
• 감염 시킬 수 없는 경우
  • 이미 다른 바이러스로 감염되어 있는 경우
  • 치료제를 가지고 있는 마을인 경우
• 입력
  • N*M 마을의 정보
  • -1 : 치료제를 가진 마을
  • 0 : 아직 감염되지 않은 마을
  • 1 : 1번 바이러스에 감염된 마을
  • 2 : 2번 바이러스에 감염된 마을
• 출력
  • 각 바이러스에 감염된 마을의 개수

접근 방법

• 전형적인 BFS 문제
  • 초기 감염된 위치를 q 에 넣고, q 에서 바이러스를 하나씩 꺼내어 주변 마을을 전염시키자
  • 인접한 마을이 아직 감염되지 않았고, 치료제가 없는 경우에만 바이러스 전차
• 바이러스 3으로 감염되는 경우?
  • 이미 바이러스에 감염되었지만 다른 바이러스와 ‘동시에’ 도착했을 경우
  • 전염 거리를 계산하여, 동시에 도착했을 경우를 고려하면 된다.

코드 설계

1. 바이러스 감염 위치 담을 q 생성 및 초기 위치 큐에 담기
2. 큐가 빌 때까지 확인
	2-1. 이미 바이러스 3으로 감염되었을 경우 인접 마을 확인 x
	2-2. 인접 마을 확인
		2-2-1. 치료제가 있는 마을인 경우 제외
		2-2-2. 감염 되지 않은 마을인 경우 감염 후 큐에 추가
		2-2-3. 이미 감염되어 있는 마을인 경우 감염 거리 같은 경우인지 확인
3. 바이러스 감염 수 카운트

코드 구현

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

N, M = map(int, input().split())
town = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
answer = [0]*4

# 1. 바이러스 감염 위치 담을 q 생성 및 초기 위치 큐에 담기
q = deque()
for i in range(N):
    for j in range(M):
        # 바이러스가 있으면 큐에 담기
        if town[i][j] > 0:
            q.append((town[i][j], i, j))

# 2. 큐가 빌 때까지 확인
while q:
    virus, y, x = q.popleft()
    # 2-1. 이미 바이러스 3으로 감염되었을 경우 인접 마을 확인 x
    if town[y][x] == 3:
        continue
    # 2-2. 인접 마을 확인
    for iy, ix in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        dy = y + iy
        dx = x + ix
        if 0 <= dy < N and 0 <= dx < M:
            if town[dy][dx] == -1:  # 2-2-1. 치료제가 있는 마을인 경우 제외
                continue
            if town[dy][dx] == 0:  # 2-2-2. 감염 되지 않은 마을인 경우 감염 후 큐에 추가
                town[dy][dx] = virus
                visited[dy][dx] = visited[y][x] + 1
                q.append((virus, dy, dx))
            # 2-2-3. 이미 감염되어 있는 마을인 경우 감염 거리 같은 경우인지 확인
            elif town[dy][dx] != virus and visited[dy][dx] == visited[y][x] + 1:
                town[dy][dx] = 3  # 3으로 감염되고 더이상 감염 퍼지지 않음

# 3. 바이러스 감염 수 카운트
for i in range(N):
    for j in range(M):
        if town[i][j] == -1:
            continue
        answer[town[i][j]] += 1

print(*answer[1:])