경쟁적 전염

문제 요약

NxN 플라스크 속에 K개 종류의 바이러스가 2차원 평면에 위치해 있고, 각 바이러스는 우선순위를 가지고 있어서 우선순위 순으로 상하좌우 퍼진다.
턴 개념으로 퍼지며 종류 후 확인 할 좌표에 있는 바이러스를 출력하는 문제

난독이 있는지 문제를 봐도 뭐라는지 모르겠다... 한참을 보고서야 뭘 요구하는지 이해가 된다.

풀이 시간: 3시간 +-

접근방법

딱 봐도 BFS 개념으로 접근하는 문제
크게 어려워 보이지 않아서 호기롭게 시작.

과정을 눈으로 보자!

입력값
N = 플라스크 크기
K = 바이러스 종류
S = time(몇 턴 진행 할 것인지)
확인 할 좌표: py,px

---

4 3		 		#N, K
2 0 0 0			#초기 플라스크 정보 입력
0 0 0 1		
0 0 0 0
3 0 0 0
2 3 2			#S, 종료 후 탐색해야 할 Y,X 좌표

---

---

코드

import sys
from collections import deque
#sys.stdin = open('input.txt','r')

# NxN 크기 시험관
# 특정 위치 바이러스 존재 - 바이러스는 1 ~ k 까지 종류
# 모든 바이러스는 1초마다 상하좌우 ( 번호가 낮은 순서)
# S초가 지난 후에 바이러스 찾기

#  N K
# 시험관 정보
# -----
# S Y-1 X-1


direction=[(1,0),(-1,0),(0,1),(0,-1)]                             #상하좌우 탐색용
n,k = map(int, sys.stdin.readline().split())
flask = []                                                        #바이러스가 담길 플라스크
virus = [a for a in range(1,k+1)]                                 #k개의 바이러스
for _ in range(n):
    flask.append(list(map(int,sys.stdin.readline().split())))
s,py,px = map(int, sys.stdin.readline().split())
q = []                                                            # 순회용 리스트 생성


for y in range(n):
    for x in range(n):
        if flask[y][x] != 0:                                       # 바이러스 속성별로 정렬이 되어야 하기에 
            q.append((flask[y][x],0,y,x))                          # 바이러스,시간,좌표 순서 튜플로 저장
q.sort()                                                           # 우선순위 큐 느낌이 되어야 하기에 q정렬
q = deque(q)                                                       # q 자료형 deque로 설정정
 
while q:
    virus,time,cy,cx = q.popleft()
    if time == s:
        break
    for dy,dx in direction:                                         # 상하좌우를 반복문으로 꺼내기
        if 0 <= cy+dy < n and 0 <= cx+dx < n and flask[cy+dy][cx+dx] == 0: # 리스트 영역 안에 있고, 상하좌우가 0이면면
            flask[cy+dy][cx+dx] = virus                             # 현재 바이러스 속성을 2차원 리스트에 추가
            q.append((virus,time+1,cy+dy,cx+dx))                    # 큐에 바이러스 추가
    

    
print(flask[py-1][px-1])

---

문제 구현에서 힘들었던 점

역시나 반례를 찾는게 많이 어려웠다.
문제와 생각을 정리하고 코드를 작성해도 작성하는 와중에 누락되는게 조금 있었다.
특히 바이러스는 각각 우선순위가 있는데
입력 받을 때, 우선순위가 높은 바이러스가 뒤에 오는 경우를 생각하지 못해서 반례를 찾는데 많은 시간을 소비해야 했다.

마치며

예제만 보고 문제를 푸는 것이 아닌 문제 내용 자체를 이해하고 요구사항에 맞게 코드를 작성하고 검토하는 습관을 들이자.