[백준,Python]7576번 토마토(Graph Search/BFS, 시간초과 해결)

[백준,Python]7576번 토마토(Graph Search/BFS)

www.acmicpc.net/problem/7576

7576번: 토마토

 

 

테스트 케이스들을 모두 통과하도록 코드를 짰지만 , 반복문이 많이 들어가서 불안했는데 '시간초과'가 발생하였다.

 

시간초과가 발생했던 코드와 개선하여 효율적으로 짠 코드를 비교해가며 이번 문제를 설명하려 한다.

 

 

1. 처음 코드( 시간 초과)

import sys
input = sys.stdin.readline

m,n = map(int, input().split())
pmap = []
#첫쨰날 ~ 끝까지 토마토 수
pcount = []
count = 0
def mapcount(pmap):
    a= 0
    for i in range(n):
        for j in range(m):
            a += pmap[i][j]
    return a
    
for _ in range(n):
    a = list(map(int,input().split()))
    pmap.append(a)
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def bfs(a,b):
    for i in range(4):
        x = a + dx[i]
        y = b + dy[i]
        if 0<=x<n and 0<=y<m and pmap[x][y] == 0:
            pmap[x][y] = 1
        
pcount.append(mapcount(pmap))
k= 0
q= []
w = []
while True:
    #하루가 지나고
    for i in range(n):
        for j in range(m):
            if pmap[i][j] == 1:
                q.append(i)
                w.append(j)
    for e in range(len(q)):
        bfs(q[e],w[e])
    
    #count += 1
    pcount.append(mapcount(pmap))
    if pcount[k] == pcount[k+1]:
        break
    k += 1
for i in pmap:
    if 0 in i:
        k = -1
        break
    else:
        pass     
print(k)

-알고리즘 :  아무 변화가 없는 상태에 탐색을 끝내야 하기 때문에, mapcount()함수를 구현하여 값들을 모두 더한 값을 계산하여 pcount 리스트에 저장시키고  pcount의 리스트값이 중복되어 나타날 경우 반복을 종료하도록 구현하였다. 또한 메인 식에 while문으로 전체 맵을 탐색하여 한번 반복이 돌 때마다 k를 1씩 증가 시켜 주도록 구현하였고, pmap[x][y]가 1인값들의 x좌표를 q라는 리스트에 넣고, y좌표를 w라는 리스트에 넣었다. 그 값들을 반복문을 사용하여 bfs함수에 넣어주는 식으로 구성하였다. 

 

2. 개선 코드(Deque사용)

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

def bfs(m,n,farm):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    count = -1

    #메인 식에서 1인 것만 deque에 담았으로 그에 대한 연산만 실행.
    while deque:
        count += 1

        for _ in range(len(deque)):
            a,b = deque.popleft()
            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]
                if 0<=x<n and 0<=y<m and farm[x][y] == 0:
                    farm[x][y] = 1
                    deque.append([x,y])
    for i in farm:
        if 0 in i:
            return -1
    return count
            
                

m,n = map(int, input().split())
deque = deque()
farm = []
for i in range(n):
    row = list(map(int,input().split()))
    for j in range(m):
        if row[j] == 1:
            deque.append([i,j])
    farm.append(row)

answer = bfs(m,n,farm)
print(answer)

-개선 코드의 알고리즘 :  deque라는 자료구조를 활용하여 메인식에서 농장이라는 맵(farm)의 값이 1인 것(i,j)들을 deque에 append시켰고, 그 deque안에 값이 있을 때에만 while 반복문들을 돌려 반복 횟수를 카운트 하도록 구현하였다. 

 

 

3. Review

-개선 코드를 짠 후 첫번째 코드의 문제점을 살펴본 결과, 반복문에서 너무 많은 시간을 잡아먹는 것이였다. while문안에서 worst case로 10^6을 잡아먹고 2중 포문으로 또 n*m인 10^6을 잡아먹으니 최악의 경우 10^9초 시간이 걸리게 된다.

따라서 2차원 리스트의 값을 반복적으로 탐색하는 문제에서는 무조건 원하는 값만을 반복해서 검사해야지 전체를 검사하게 되면 시간초과가 발생한다. 그 방법으로 이번 문제에서는 queue보다 속도 측면에서 빠른 deque라는 collections의 라이브러리를 활용하게 되었다.