1. 문제 출처
https://www.acmicpc.net/problem/18405
2. 풀이
해당 문제는 1 ->2->....->K 순으로 바이러스가 움직이기 때문에 2차원 리스트을 queue처럼 이용하고자 하였으나, 그것보다 temp라는 3차원 배열에 코드와 같이 index + 1 과 같은 바이러스 번호를 가진 좌표를 모으고 2차원으로 펴준 queue를 생성한다. 그러면 자동적으로 바이러스 번호가 작은 순으로 나오게 된다.
예시)
1 | 2 | |
4 | 3 |
-> [ [ [1,1,1] ], [ [ 1,3,2] ] , [ [3,3,3 ] ], [ [ 3,1,4] ] ] - > [ [1,1,1] , [ 1,3,2]] , [ 3,3,3 ], [ 3,1,4] ] ]
# 입력값 받기
N,K = map(int,input().split())
test = [[] for _ in range(N)]
for idx in range(N):
test[idx] = list(map(int,input().split()))
# 원점의 기준이 1,1 이므로 1씩 빼준다.
S,X,Y = map(int,input().split())
X -= 1
Y -= 1
# 상하좌우 좌표이동
dx = [0,0,-1,1]
dy = [-1,1,0,0]
# 너비우선 탐색
def bfs():
# 바이러스 번호대로 정렬 하기 위해 다음과 같이 한다.
temp = [[]for _ in range(K)]
for i in range(N):
for j in range(N):
# test[i][j] 가 0이 아니라면
if test[i][j] !=0:
#test[i][j] - 1 을 인덱스로 하는 value에 [i,j,test[i][j]]을 추가한다.
temp[test[i][j]-1].append([i,j,test[i][j]])
queue = []
# temp 를 2차원 배열로 펴준다.
for t in temp:
queue +=t
# 경과 시간
sec = 0
# 맨 처음 바이러스 번호
first_num = queue[0][2]
# 저번에 실행한 바이러스 번호
back_num = 0
# 경과 시간이 S가 되거나 queue가 비면 반복 종료
while (sec != S) and (queue):
x,y,virus_num=queue.pop(0)
# 만약 1~K 까지의 바이러스 증식이 1번 반복 되면 경과 시간에 1초를 추가한다.
if (back_num != virus_num )and (virus_num == first_num):
sec+=1
# 증식된 좌표 구하기
for idx in range(4):
move_x = x + dx[idx]
move_y = y + dy[idx]
# 만약 증식된 좌표가 X,Y 이면 바이러스 번호를 출력하고 종료
if move_x == X and move_y ==Y :
print(virus_num)
return
# 증식 가능한 빈자리이면 증식 후 queue에 추가
if 0<=move_x<N and 0<=move_y<N:
if test[move_x][move_y] == 0:
test[move_x][move_y] = virus_num
queue.append([move_x,move_y,virus_num])
back_num = virus_num
print(test[X][Y])
bfs()
'알고리즘 > 너비 우선 탐색(bfs)' 카테고리의 다른 글
16236-백준-아기상어 (0) | 2023.03.01 |
---|---|
16234-백준-인구이동 (0) | 2023.02.23 |
18352-백준-특정 거리의 도시 찾기 (0) | 2023.02.17 |
14502 - 백준 - 연구소 (0) | 2023.02.15 |
9205-백준-맥주 마시면서 걸어가기 (0) | 2023.02.07 |