dfs&bfs-(2)

1. 경쟁적 전염 => bfs 사용문제[8/6]

18405번: 경쟁적 전염

오답이유

1. 틀렸습니다 : 1-k까지의 바이러스의 종류가 있고 바이러스 개수는 k개로 정해진 것이 아닌데 한종류의 바이러스가 1번만 들어왔을때 체크하도록 코드를 작성하였음 => 다른 부분에서 error가 나는 줄 알고 계속 시도했다가 틀렸었고, 해당 이유를 찾을 수 있었던 testcase를 아래코드 밑에 넣어둠.

2. 출력초과 : list를 print해본 코드를 주석 혹은 삭제처리 하지 않았기 때문에 발생

3. 한 종류의 바이러스가 여러번 들어올 수 있기 때문에 종류(바이러스 번호)를 가지고 sort를 먼저함. 이후 sort된 list를 가지고 바이러스의 x,y좌표를  queue에 append할때 바이러스의 종류의 순서대로 넣어고 while을 돌려줌

 

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

from collections import deque
#입력받기
n,k = map(int, input().split())
map_list = []
for i in range(0,n):
    map_list.append(list(map(int,input().split())))
s,X,Y = map(int, input().split())

#x,y,바이러스번호를 기억할 queue를 생성
queue_x = deque()
queue_y = deque()
queue_num = deque()

def queue_append(x,y,num):
    queue_x.append(x)
    queue_y.append(y)
    queue_num.append(num)
    map_list[x][y]=num


def bfs(cnt,befor):
    while queue_x:
        x = queue_x.popleft()
        y = queue_y.popleft()
        num = queue_num.popleft()
        #아래의 조건은 마지막 종류의 바이러스가 before을 줄인 befor에 넣어놓고 현재 바이러스가 1일때 1초를 더해주는 시간 계산코드
        if befor==k and num==1:
            cnt+=1
        if cnt==s:
            return
        befor = num
        #아래의 4개의 조건문은 상하좌우로 퍼져나가게끔 하는 코드
        if x-1>=0 and map_list[x-1][y]==0:
            queue_append(x-1,y, num)
        if x+1<n and map_list[x+1][y]==0:
            queue_append(x+1,y,num)
        if y-1>=0 and map_list[x][y-1]==0:
            queue_append(x,y-1,num)
        if y+1<n and map_list[x][y+1]==0:
            queue_append(x,y+1,num)
        

be_list=[]
#정렬을 위해 be_list를 사용

for i in range(0,n):
    for j in range(0,n):
        if map_list[i][j]!=0:
            be_list.append([i,j,map_list[i][j]])

be_list.sort(key = lambda x:x[2])

for i in range(0,len(be_list)):
            queue_x.append(be_list[i][0])
            queue_y.append(be_list[i][1])
            queue_num.append(be_list[i][2])
            #위의 세개도 역시 queue_append()를 사용해서 나타낼 수도 있음

bfs(0,-1)
print(map_list[X-1][Y-1])

# '틀렸습니다'가 나왔던 이유를 알 수 있었던 testcase예제를 찾아봄
'''
5 2
1 0 0 0 2
0 0 1 0 0
2 0 0 0 0
0 0 0 0 0
0 0 0 0 1
3 3 3
'''

---