18405-백준-경쟁적 전염

1. 문제 출처

https://www.acmicpc.net/problem/18405

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()