[백준 15806번] 영우의 기숙사청소(파이썬)

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

15806번: 영우의 기숙사 청소

이 문제는 무식하게?풀면 바로 시간초과가 뜹니다.

제가 처음풀었던 풀이입니다.

 

#백준 15806번 영우의 기숙사청소

N,M,K,t=map(int,input().split())
dir=[(-2,-1),(-2,1),(-1,2),(-1,-2),(1,-2),(1,2),(2,-1),(2,1)]
virus=[]
check=[]
for _ in range(M):
    a,b=map(int,input().split())
    virus.append((a-1,b-1))

for _ in range(K):
    c,d=map(int,input().split())
    check.append((c-1,d-1))



day=0

no_v=False
while day<t:
    day+=1
    if not virus:
        no_v=True
        break
    new=set()
    for x,y in virus:
        for d in range(8):
            nx=x+dir[d][0]
            ny=y+dir[d][1]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue

            new.add((nx,ny))
    virus=[]
    for px,py in new:
        virus.append((px,py))


if no_v:
    print("NO")
    exit(0)

for cx,cy in check:
    if (cx,cy) in virus:
        print("YES")
        exit(0)

print("NO")

 

문제에서 요구하는데로

우직하게 구현했더니

시간초과가 났습니다.

 

이 문제는 bfs로 풀어야 시간초과 없이

정답을 맞출 수 있습니다.

 

그럼 어떻게 bfs로 풀 수 있냐.

이런식으로 생각하면

홀/짝을때를 나눠서 생각할 수 있습니다.

 

여기서 주의할 점은

바이러스가 퍼지지 않는 경우입니다.

이걸 구현안하면

 

3 1 1 2

2 2

2 2

이 반례가 틀렸다고 뜹니다.

왜냐하면 바이러스는 하루 지났을때

벽에 막혀 이미 사라졌는데,

바이러스가 퍼지지 않는 경우를 구현하지 않으면

그대로 남아있는 걸로 처리가 되버립니다.

#백준 15806번 영우의 기숙사청소
from collections import deque
N,M,K,t=map(int,input().split())
dir=[(-2,-1),(-2,1),(-1,2),(-1,-2),(1,-2),(1,2),(2,-1),(2,1)]
q=deque()
check=[]
visited=[[[False]*2 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    q.append((a-1,b-1,0))
    visited[a-1][b-1][0]=True

for _ in range(K):
    c,d=map(int,input().split())
    check.append((c-1,d-1))
#바이러스는 홀/짝으로 퍼짐
#홀수일때 짝수일때 바이러스가 각각 다르다
while q:
    x,y,day=q.popleft()
    if day>=t:
        continue
    v_c=False
    for d in range(8):
        nx=x+dir[d][0]
        ny=y+dir[d][1]

        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue
        next=(day+1)%2
        if visited[nx][ny][next]==True:
            continue
        visited[nx][ny][next]=True
        q.append((nx,ny,day+1))
        v_c=True
    #만약 바이러스가 안퍼짐
    #-->다시 그 자리로 못온다
    #결국 그 바이러스는 없어짐
    if not v_c:
        visited[x][y][(day%2)]=False

c=t%2
for cx,cy in check:
    if visited[cx][cy][c]==True:
        print("YES")
        exit(0)

print("NO")

bfs를 어떻게 풀 수 있을지 생각하게 만들어주면서

문제의 조건도 세심하게 따져볼 수 있는 좋은 문제입니다.

문제에서 주어진 아이디어를 잘 정리할 필요가 있어 보입니다.