[백준] 7576 - 토마토 (Python)

문제 출처 :

www.acmicpc.net/problem/7576

7576번: 토마토

문제 풀이 :

• BFS로 문제를 풀었다. 다른 문제들도 그렇지만 (미로탐색 문제라던지 앞에 풀었던 다른 BFS문제들 처럼) 이 문제와 같이 일련의 단계를 끝내고 시간, 횟수를 +1 하는 경우에는 나는 대부분 deque(혹은 stack) 자료 구조를 2개 를 사용한다.
• 각각을 1번 ,2번 dq라고 본다면 
  1번 dq에 대한 while문 , 2번 dq에 대한 while문을 작동 시킨다.
• 1번 dq가 끝나면 문제에서 말하는 일련의 단계가 끝나고 날짜(혹은 시간, 횟수 등)이 추가되어야 한다고 생각해서 추가해주고 다시 1번 dq를 작동시키기 위한 코드를 돌리고 (2번 dq while문에서) 기저사례를 만날 때 까지 반복한다.
• 말로만 하면 이해가 안되니까 예제를 가져와서 보자면

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

time :0

dq : [(4,6)]
next_dq : [()]
(코딩에선 -1,-1 한 좌표를 썻지만 여기선 편의상 그냥 쓰겟다)
(문제에서 입력이 가로 세로에 대한 index가 다른 문제랑 다르니 주의해야한다. 필자도 이부분에서 코드가 꼬여 시간을 낭비했다.)

 

dq 에 대해서 while문 BFS를 돌린다 이후 dq가 비어서 while이 끝나면 time +=1 을 해준다. dq에 대해 BFS 탐색할때 갈 수 있는 곳은 next_dq에 저장해준준다.

 

즉,

time :0

dq :[]

next_dq : [(5,4),(6,3)]

이 되고 time +1 이후 next_dq값을 dq로 넘어주며 next_dq와 dq가 모두 빌 때 까지나 기저사례를 만날때까지 반복한ㄴ다.

 

time :1

dq : [(5,4),(6,3)]

next_dq : [()]

 

• 필자는 기저사례에 대해서 미리 맵 전체에서 0의 갯수(익지않은 토마토의 갯수) 를 cnt 변수에 넣어두고 cnt가 0이하가 되는 순간을 기저사례로 선택해서 코딩햇다.

import numpy as np

from collections import deque

m,n = map(int,input().split())
farm = [list(map(int,input().split())) for _ in range(n)]

def bsf_tomato():
    global farm,n,m
    visited = [[0]*m for _ in range(n)]
    dq = deque()
    cnt =0

    for i in range(n):
        for j in range(m):
            if(farm[i][j]==1):
                dq.append((i,j))
                visited[i][j]=1
            if(farm[i][j]==0):
                cnt+=1
    time =0
    next_dq = deque([1])
    dn = [1,0,-1,0]
    dm = [0,1,0,-1]
    if(cnt<=0):
        print(0)
        return 0

    while(next_dq):
        next_dq=deque([])
        while(dq):
            cur_n,cur_m = dq.popleft()
            for i in range(4):
                nn = cur_n+dn[i]
                nm = cur_m+dm[i]
                if(nn>=n or nn<0 or nm<0 or nm>=m):
                    continue
                if(farm[nn][nm]==0 and visited[nn][nm]==0):
                    visited[nn][nm]=1
                    farm[nn][nm]=1
                    next_dq.append((nn,nm))
                    cnt-=1
                    if(cnt==0):
                        print(time+1)
                        return 0
        dq=next_dq
        time+=1

        # print(np.array(farm))
        # print()

    print(-1)
    return 0

bsf_tomato()