문제

BOJ 18405: 경쟁적 전염 https://www.acmicpc.net/problem/18405

풀이

조건

• 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
• 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다.
• 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
• S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력한다.
• 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

풀이 순서

• BFS를 사용한다.
• 초기 바이러스의 정보를 list에 담는다.
  • 바이러스의 정보 : 바이러스의 번호, 퍼진 시간, 행 좌표, 열 좌표
• 위의 list를 오름차순 정렬한 뒤 deque으로 변환한다.
  • 바이러스의 번호를 기준으로 오름차순 정렬한다.
  • BFS를 사용하기 위해 deque으로 변환한다.
• 아래 코드와 주석처럼 탐색을 한 뒤 목표 시간이 되면 종료하고 답을 출력한다.

코드

Python

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S, X, Y = map(int, sys.stdin.readline().split())

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

time = 0
arr = list() # 초기 바이러스의 정보를 담을 리스트
for i in range(N):
    for j in range(N):
        if board[i][j] != 0:
            arr.append([board[i][j], time, i, j])

arr.sort() # 바이러스 번호를 기준으로 오름차순 정렬함
que = deque(arr) # 초기 바이러스의 정보가 담긴 리스트를 deque으로 변환

while que:
    now = que.popleft()

    nowValue = now[0] # 바이러스 번호
    nowTime = now[1] # 바이러스가 퍼졋던 시간
    nowX = now[2] # 바이러스의 행 좌표
    nowY = now[3] # 바이러스의 열 좌표
    
    # 목표 시간이 되면 탐색 종료
    if nowTime == S:
        break

    # 4 방향 탐색
    for t in range(4):
        nx = nowX + dx[t]
        ny = nowY + dy[t]
        # 범위 체크
        if nx < 0 or ny < 0 or nx >= N or ny >= N:
            continue
        # 해당 위치에 다른 바이러스가 있는지 체크
        if board[nx][ny] != 0:
            continue
        # que에 바이러스 삽입
        que.append([nowValue, nowTime + 1, nx, ny])
        # 연구소에 해당 바이러스 번호 입력
        board[nx][ny] = nowValue
    time += 1 # 시간 +1

print(board[X-1][Y-1])

정리

• 처음엔 PriorityQueue를 사용해서 해결하려 했지만 시간초과가 났다.
• 바이러스의 초기 상태만 조건에 맞춰 정렬한 뒤 deque으로 변환해 BFS를 구현하면 된다는 것을 알았다.