[ 백준 18405 해설 ] ( python ) 경쟁적 전염

 

📚 경쟁적 전염

 

문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

 

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

 

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

 

예제 입력 1 복사

3 3
1 0 2
0 0 0
3 0 0
2 3 2

예제 출력 1 복사

3

예제 입력 2 복사

3 3
1 0 2
0 0 0
3 0 0
1 2 2

예제 출력 2 복사

0

 

 

 

 

✍ 접근

• BFS
• 토마토 문제에서 아이디어를 떠올렸다. 처음에 바이러스의 위치를 저장해둔다
• deque나 heapq나 별 상관 없을 것 같지만 번거롭게 sort를 하고 싶지 않아서 heapq를 이용했다
• 반례
  4 1000
  1 2 3 4
  7 6 5 1000
  8 9 10 120
  160 110 130 2
  3 4 3
  예제가 다 맞더라도 안되면 이 반례를 넣어보세요

 

 

 

 

정답코드

# ✨ 입력
import sys
import heapq
N,K = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
S,X,Y = map(int,input().split())

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

# ✨ 준비
hq = []
for i in range(N):
    for j in range(N):
        if board[i][j] !=0:
            heapq.heappush(hq,(0,board[i][j],i,j))

# ✨ BFS
def BFS():
    while hq:
        t,v,x,y = heapq.heappop(hq)
        if t >= S:
            print(board[X-1][Y-1])
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N and board[nx][ny] == 0:
                board[nx][ny] = v
                heapq.heappush(hq,(t+1,v,nx,ny))
    if t < S:
        print(board[X-1][Y-1])

BFS()

 

해설

입력

• 문제에서 나온 값을 입력받는다

준비

• 이중 fo문을 통해 board를 돌면서 바이러스가 발견되면 hq에 heappush해준다.
• 맨 처음 0은 time, 두번째 인자는 바이러스의 번호, 그리고 좌표

BFS

• hq가 있을 때 heappop을 하고
• 만약 t가(시간)이 S보다 같거나 클 경우 print해준다
• for문을 통해 상하좌우를 탐색하면서 
  • 아직 아무 바이러스가 접근하지 못한 곳을 발견하면 v로(당시 가장 작은 바이러스로) 업데이트해준다
  • 그리고 heappush
• 🚨 만약 while문을 다 돌았는데도 t<S라면? (위의 반례)
  그러면 시간이 S까지 흐르기도 전에 모든 시험관이 바이러스로 채워진 것이므로 그냥 print한다

 

 

⭐ 배움

• 예외처리