[백준]18405(파이썬) - 경쟁적 전염

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

18405번: 경쟁적 전염

 

• 이 문제는 94퍼센트 정답률 까지는 10분 안에 풀었지만 나머지 반례를 찾지 못해서 꽤 시간이 걸린 문제입니다..
• 나머지 6퍼센트가 어느 부분에서 잘못 되었는지는 파악이 되었습니다. 바로 1초가 지난 후 시험관의 상태를 체크할 때, 어떻게 체크할 것이냐의 문제였던 것 같은데요, 제가 처음 풀었던 풀이에서 어디가 잘못되었는지 아시는 분은 댓글 부탁드립니다ㅠㅠ
• 결국에는 시간 체크를 다른 방법으로 생각해서 풀긴 풀었는데요, for문이나 while문을 돌면서 시간을 체크하는 것이 아닌 어쨌든 한 번 체크를 당하고 BFS를 이용한 풀이에서 q 로 들어갈 때 이전에 가지고 있던 Time 에서 +1 을 해서 append 시켜주는 방식을 사용했습니다. 나머지 구현은 어렵지 않았습니다.

 

import sys
input = sys.stdin.readline
from collections import deque

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

graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
s,x,y = map(int,input().split())

#bfs 문제
# 상,하,좌,우 번호가 낮은 종류의 바이러스부터 증식.
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bfs():
    virus = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                virus.append((graph[i][j],0,i,j))
    virus.sort(key=lambda x: x[0])
    q = deque(virus)
    while q:
        num,time,x,y = q.popleft()
        if time == s:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0<= ny < n and graph[nx][ny] == 0:
                graph[nx][ny] = num
                q.append((num,time+1,nx,ny))

bfs()
print(graph[x-1][y-1])

 

 

아래는 제가 첫 번째로 풀었던 풀이입니다. 어느 부분이 틀렸는지 아시는 분은 댓글 부탁드립니다ㅠㅠ 아님 반례 테스트케이스라도...

 

import sys
input = sys.stdin.readline
from collections import deque

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

graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
s,x,y = map(int,input().split())

#bfs 문제
# 상,하,좌,우 번호가 낮은 종류의 바이러스부터 증식.
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def bfs():
    virus = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                virus.append((graph[i][j],i,j))
    len_vir = len(virus)
    virus.sort(key=lambda x: x[0])
    cnt = 0
    result = 0
    while virus:
        num,x,y = virus.pop(0)
        if num > k:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0<= ny < n and graph[nx][ny] == 0:
                graph[nx][ny] = num
                virus.append((num,nx,ny))
                cnt += 1
        if cnt == len_vir-1:
            cnt = 0
            result += 1
        if result == s:
            break
        
        
bfs()
print(graph[x-1][y-1])