백준18401
이코테 345p

문제

입출력

• 제한
  • 시간 1초 / 메모리 256MB
• 입력
  • 첫째줄 : 자연수 N, K
    (1<=N<=200 , 1<=K<=1000)
  • 둘째줄 ~ : 시험관 정보
    바이러스 정보 (K이하 int_ / 존재하지 않는 경우 0으로 주어짐
• 출력
  • S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력.
    S초 뒤에 해당 위치에 바이러스 존재하지 않으면 0 출력

상황

• N*N 크기의 시험관이 있음
• 바이러스의 종류는 1~K 번까지
• 바이러스는 1초마다 상/하/좌/우 로 증식함
• 번호가 낮은 바이러스 먼저 증식하며 & 이미 어떤 바이러스가 있다면 그 자리에 다른 바이러스가 증식할 수없다.

-> 특정 좌표 (X,Y)에 S초 뒤에 어떤 바이러스가 있는지 출력하시오

풀이

풀이 아이디어

• BFS를 활용하면, S초가 지남에 따른 갈수 있는 범위를 셀 수 있다는 것 ! !
  • 이런 아이디어는 도달할 수 있는 최단거리에 BFS를 활용한 아이디어를 다른방식으로 활용한 것이다.
• 낮은 번호 부터 증식 = 큐에 먼저 넣는다는 생각

코드

from collections import deque

n, k = map(int, input().split())

graph = []
data = []

for i in range(n) :
	# 보드 정보를 한 줄 단위로 입력
	graph.append(list(map(int, input().split())))
	for j in range(n) :
		# 해당 위치에 바이러스 존재하는 경우
		if graph[i][j] != 0 :
			# (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입
			data.append((graph[i][j], 0, i, j))

# 정렬 이후에 큐로 옮기기 (낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data) # 큐 생성

target_s, target_x, target_y = map(int, input().split())

# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 너비 우선 탐색(BFS) 진행
while q :
	virus, s, x, y = q.popleft()
	# 정확히 S초 지나거나, 큐가 빌때까지 반복
	if s == target_s :
		break
	# 현재 노드에서 주변 4가지 위치를 각각 확인
	for i in range(4) :
		nx = x + dx[i]
		ny = x + dy[i]
		# 해당 위치로 이동할 수 있는 경우
		if 0 <= nx and nx < n and 0 <= ny and ny < n :
			# 아직 방문하지 않ㅇ느 위치라면, 그 위치에 바이러스 넣기
			if graph[nx][ny] == 0 :
				graph[nx][ny] = virus
				q.append((virus, s+1, nx, ny))

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