[bfs/백준] 18405번: 경쟁적 전염

-문제: https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

변수명 겹치지 않게 잘 사용하기(이거 때문에 여러번 틀렸다)

 

-정답풀이: 

from collections import deque
n,k=map(int,input().split())
data=[]
virus=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(n):
    data.append(list(map(int,input().split())))
    for j in range(n):
        if data[i][j]!=0:
            virus.append((data[i][j],0,i,j))
virus.sort()
q=deque(virus)

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

while q:
    germ, s, x, y = q.popleft()
    if s == target_s:
        break
    for i in range(4):
        for j in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if data[nx][ny]==0:
                    data[nx][ny]=germ
                    q.append((germ, s+1, nx, ny))
print(data[target_x -1][target_y -1])

 

-내가 시도한 풀이 

i번 바이러스에 대한 정보 담는 방법이 미흡했다

그리고 바이러스 순서대로 하면 겹칠 가능성 없다

from collections import deque
n,k=map(int,input().split())
data=[]
virus=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(n):
    data.append(list(map(int,input().split())))
    for j in range(n):
        for l in range(1,k+1):
            if data[i][j]==l :
                virus[l].append([i,j])
s,x,y=map(int,input().split())
def bfs(u,v,k,s):
    q=deque()
    q.append((u,v))
    time=0
    while q:
        if time ==s:
            break
        x,y= q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if data[nx][ny]==0 or data[x][y]<data[nx][ny]:
                    data[nx][ny]=k
                    q.append((nx,ny))
                else:
                    continue
        time+=1
for i in range(1,k+1):
    if len(virus[i]) !=0:
        a,b=virus[i]
        bfs(a,b,i,s)
        
print(data[x-1][y-1])