[7576- BOJ] 토마토 - BFS

백준 7576번 토마토 문제에 대한 포스팅을 올리겠습니다.

 

문제정의

---

이는 전형적인 BFS 문제입니다. 

N x M의 상자를 입력받고, 상자 내에 토마토(1아니면 0), 칸막이(-1)의 값을 입력받습니다. 

예시 그림

1의 경우 익은 토마토, 0은 익지 않은 토마토를 뜻합니다. 특이한 것은 보관 후 하루가 지나면 1에 인접한(좌,우,위,아래 4방향) 익지않은 토마토들이 모두 익은 토마토로 변합니다(인접한 0의 원소들이 전부1로 변하는 과정입니다). 이렇게 기존 익은 토마토들에 인접한 익지 않은 토마토들이 익는데 하루(+1)가 걸린다고 가정합시다. 그리하여 상자 내의 모든 토마토가 1이 되는데 어느정도의 시간이 걸리는지 구하는 문제입니다.

 

 

 

입출력 정의

---

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 입니다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어집니다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어집니다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타냅니다.

토마토가 하나 이상 있는 경우만 입력으로 주어집니다.

 

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 합니다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

입력
출력	8	-1	6

입력
출력	14	0

 

코드 작성 및 리뷰

---

기본적인 입출력은 미리 전처리 하였다고 가정하고 프로그래머스 스타일로 코드리뷰를 하겠습니다. 

from collections import deque

def solution(arr):
    aj_list = deque()
    max_row = len(arr)
    max_col = len(arr[0])
    for ri in range(0,max_row):
        for ci in range(0,max_col):
            if arr[ri][ci]==1: 
                aj_list.append((ri,ci))
        else:
            continue
    if len(aj_list) ==0:
        return -1

먼저 익은 사과들의 위치(1)를 먼저 찾습니다. 만약 사과가 하나도 익지않았다면, 진행할 수 없으므로 -1을 리턴합니다.

    count=0
    tmp_ad_list = deque()
    while(len(aj_list)>0):       
        r,c = aj_list.popleft()
        rr,lr,hc,lc = None,None,None,None

본 문제는 BFS방식으로 풀도록 의도되어진 문제이기 때문에 인접한 사과들을 저장할 리스트가 필요합니다. 따라서 tmp_ad_list를 만들어서 현재 익은 사과를 저장하는 리스트를 만들어줍니다. 그리고 현재 익은 사과와 인접한 사과들에 대한 정보를 수집해야하므로, pop연산을 통해 현재 사과의 좌표를 aj_list에서 제거합니다.

 이제 위,아래,좌,우 4방향만 고려하면 되므로 이를 위한 4방향을 검사하는 변수를 초기화합니다.

DFS와 BFS 나무위키펌

        if r+1<max_row:
            rr=r+1
            if  arr[rr][c]==0:
                tmp_ad_list.append((rr,c))
                arr[rr][c]=1

        if r-1>=0:
            lr=r-1
            if arr[lr][c]==0:
                tmp_ad_list.append((lr,c))
                arr[lr][c]=1
                    
        if c+1 <max_col:
            hc= c+1
            if arr[r][hc]==0:
                tmp_ad_list.append((r,hc))
                arr[r][hc]=1
                
        if c-1>=0:
            lc=c-1
            if  arr[r][lc]==0:
                tmp_ad_list.append((r,lc))
                arr[r][lc]=1

위에서 정의한 위,아래,좌,우 4방향만 고려하면 되므로 이를 확인하고 안익은 사과일경우 새롭게 익은 사과가 되는 사과의 좌표들을 tmp_ad_list에 저장합니다. 그후 새로 익은 사과로 바꾸어 줍니다.

        if len(aj_list)==0:
            count+=1
            if len(tmp_ad_list)>0:
                aj_list.extend(tmp_ad_list)
                tmp_ad_list.clear()
            else:
                for r in arr:
                    if 0 in r:
                        return -1
                return count-1

현재 익은 사과 리스트(aj_list)가 비어있다면, 오늘 하루가 지난것으로 간주합니다. 하여 오늘 새로이 익은 사과를 저장한 리스트(tmp_ad_list)를 그대로 복사합니다. 이는 BFS가 새로 탐색한 지역을 업데이트하는 것에 해당합니다.(Count +1 하루가 지남을 의미)

그러나 현재 익은 사과 리스트가 비어있지 않은 것은, 아직 탐색해야할 사과가 남은 것이므로 그냥 지나칩니다.

 

추후 현재 익은 사과 리스트(ad_list)도 0이고 새로이 익슨 사과를 저장한 리스트(tmp_ad_list)가 0인 경우는 모든 탐색이 끝난 경우를 의미합니다. 빈 리스트는 사과가 익는데 걸리는 시간이 아니므로 최종출력에서 -1을 빼줍니다.

그러나 모든 탐색을 마쳤는데 벽에 막혀서 안익은 사과가 있다면 문제 정의에 따라 -1을 출력합니다.

반례모음

---

 

ex_arr_1 = [
    [0,-1],
    [-1,0]
    ]
 ### Expected -1
    
ex_arr_2 = [
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0]
    ]
### Expected 5

ex_arr_3 = [
    [1, 0,-1, 0, 0]
    ]
### Expected -1

ex_arr_4 = [
    [1, 0, 0, 0, 0, 0],
   [-1, -1, -1, -1, -1, -1],
    [-1, 0, 0, 0, 0, 0],
    [-1, 0, 0, 1, 0, 0],
    [-1, 0, 0, 0, 0, 0]
    ]
### Expected 5

ex_arr_5 = [
    [1, 0, 0],
[0 ,0, -1],
[0, -1, 0]
    ]
### Expected -1

아래는 코드 제출 결과입니다.

제출한 결과

Reference 

---

https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

7576번: 토마토

P.S

---

저의 길고 길었던 대학원 시간이 끝나가는 시기입니다. 박사를 할지 사회로 나갈지 고민하다가 앞으로 개발을 하면서 살고싶다는 생각이 들었습니다. 물론 그동안 읽었던 논문과 학문적인 지식을 제가 만드는 프로젝트에 담아내면서 살아가고 싶습니다 ㅋㅋ 앞으로 취준을 해야해서 알고리즘 공부를 시작했고, 주변 지인들이 블로그를 아주 잘 활용하는 것을 보았고, 저역시 저의 일상을 담고 저만의 서고 느낌으로 꾸미고 싶습니다. 오랜만에 코딩을 해서 변수명을 대충지어서 보기 불편하셨다면 죄송합니다.. 다음부턴 신경쓸게요 ㅜㅜ