[백준 24513] 좀비바이러스(파이썬)

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

24513번: 좀비 바이러스

많이 본 bfs유형과 같지만 다릅니다.

1,2 바이러스가 있고

1,2바이러스가 동시에 퍼집니다.

'동시에'퍼진다는 것 때문에

'동시에'퍼트리는 걸 구현해야합니다.

 

"아니, 동시에 퍼지니깐 동시에 퍼지죠.

그게 뭔소리이신가요?"

 

만약 이 문제가

'바이러스가 퍼진다'라고 했으면

바이러스를 queue에 넣고

bfs계속 돌려주면 문제가 없습니다.

그런데 1,2 각각의 바이러스가 다르고

특히나 1,2가 겹칠때 생기는 3번이 있습니다.

 

그래서 이렇게 구현해주면 됩니다.

 

1. 현재 1 바이러스 상하좌우 다 구하기

2. 현재 2 바이러스 상하좌우 다 구하기

3. 겹치는 거는 3으로 만들고

안겹치는 건 각각 1과2로 만들기

#백준 24513번 좀비바이러스
from collections import deque

N,M=map(int,input().split())
room=[]
dx=[0,0,1,-1]
dy=[1,-1,0,0]

ox,oy=-1,-1
tx,ty=-1,-1
one=[]
two=[]

v=[0,deque(),deque()]
for x in range(N):

    tmp=list(map(int,input().split()))
    for y in range(M):
        if tmp[y]>0:
            v[tmp[y]].append([x,y])
    room.append(tmp)
one_cnt,two_cnt,three_cnt=1,1,0


while v[1] or v[2]:
    tmp1=set()
    tmp2=set()
    #바이러스를 퍼트린다
    #1번 바이러스 먼저.

    for _ in range(len(v[1])):
        x,y=v[1].popleft()

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

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

            if room[nx][ny]==0:
                tmp1.add((nx,ny))

    #2번 바이러스

    for _ in range(len(v[2])):
        x, y = v[2].popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

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

            if room[nx][ny]==0:
                tmp2.add((nx, ny))

    #겹치는 건 3으로 만들어준다
    tmp3=tmp1&tmp2
    for x,y in tmp3:
        room[x][y]=3
        three_cnt+=1
    for x,y in tmp1-tmp2:
        room[x][y]=1
        v[1].append([x,y])
        one_cnt+=1
    for x,y in tmp2-tmp1:
        room[x][y]=2
        v[2].append([x,y])
        two_cnt+=1



print(one_cnt,two_cnt,three_cnt)

처음에 1과 2 바이러스 지역을

리스트로 받아서 했으나

집합 set을 활용해서

바로바로 구하는 방법을 써야지

시간초과가 안걸리더라고요.

이 문제로 set을 쓰는 방법도 직접적으로 익힐 수 있었습니다.