[이코테] DFS/BFS 문제 - 경쟁적 전염

난이도 : ●●○ | 풀이 시간 : 50분 | 시간 제한 : 1초 | 메모리 제한 : 256MB | 기출 : 핵심 유형

 

문제

• N x N 크기의 시험관이 있다.
• 특정 위치에는 바이러스가 존재할 수도 있다.
• 바이러스의 종류는 1~K번까지 K가지가 있고 모든 바이러스는 이중 하나에 속한다.
• 시험관에 존재하는 모든 바이러스는 1초마다 상하좌우 방향으로 증식한다.
• 매초 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
• 이미 바이러스가 있는 곳에는 다른 바이러스가 들어갈 수 없다.
• S초가 지난 후 (X, Y)에 존재하는 바이러스의 종류를 출력하라.
• S초가 지난 이후에 해당 바이러스가 존재하지 않으면 0을 출력한다.
• X와 Y는 각각 행과 열의 위치를 의미한다.

https://www.acmicpc.net/status?user_id=dewchae45&problem_id=18405&from_mine=1

채점 현황

 

입력조건

• 첫째 줄에 자연수 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)에 존재하는 바이러스의 종류를 출력한다.
• (X,Y)에 바이러스가 존재하지 않으면 0을 출력한다.

 

입력예시

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

출력예시

3

 

아이디어

• 시험관 정보를 입력받을 때 바이러스가 존재하는 곳의 정보를 따로 큐에 저장한다.
  • data라는 리스트를 만들고 (바이러스번호, x, y,시간->초기에는 0)를 추가한다.
• 입력을 마친 뒤 data.sort()를 해서 바이러스번호의 오름차순으로 정렬한다. 
  • 이 큐를 사용해 BFS탐색을 하면 자연스럽게 번호가 낮은 바이러스부터 증식하게 된다.
• 시간이 s초만큼 흐르거나, 큐가 다 빌 때까지 BFS 탐색을 한다.
• (X, Y)에 저장된 바이러스번호를 출력한다.

 

코드

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

n,k = map(int,input().split())
graph = []
data = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
    	# 바이러스라면 바이러스번호, x좌표, y좌표, 시간-> 초기에는 0
        if graph[i][j]!=0:
            data.append((graph[i][j],i,j,0))

data.sort()
q = deque(data)

target_s,target_x,target_y = map(int,input().split())
    
while q:
     v,x,y,s = q.popleft()
     if s==target_s:
          break
     for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny]==0:
                    graph[nx][ny] = v
                    q.append((v,nx,ny,s+1))

print(graph[target_x-1][target_y-1])

 

 

출처

이것이 취업을 위한 코딩테스트다 with 파이썬