[Python 파이썬]백준 7576번 - 토마토

2023년 9월 22일

문제 링크 : 백준 7576번 - 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

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

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

출력

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

문제 접근

해당 문제는 암시적 그래프를 활용해야 하는 문제이다. 최초 1인 좌표를 시작으로 주변의 0인 좌표를 찾아 하루가 지날수록 1로 만들어 마치 전염시키는 그림을 그리는 것이 목표이다.

 

암시적 그래프를 활용해야 하고, 어떤 방식을 사용하든 해당 그래프를 탐색해야 한다. 여기서, 문제에 나와있듯 익은 토마토와 인접한 아직 익지 않은 토마토가 영향을 받는데 여기서 '인접한' 이란, 익은 토마토를 기준으로 상, 하, 좌, 우를 의미한다. (대각선은 영향을 끼치지 않는다는 의미)

이 점에서 우리는 특정 좌표에서 다른 좌표로 뻗어나갈 수 있는지 확인하기 위해 상, 하, 좌, 우로 이동을 한 칸씩 해봐야 하니 다음과 같은 요소가 코드에 추가되어야 함을 추측할 수 있다.

 

# dx : x축(좌/우)으로 이동을 담당
dx = [1, 0, -1, 0]

# dy : y축(상/하)으로 이동을 담당
dy = [0, -1, 0, 1]

 

그렇다면 dx, dy로 어떻게 특정 좌표에서 상, 하, 좌, 우로 한 칸씩 움직이는가? 다음과 같이 움직일 수 있다.

 

# 예시를 위해 [2, 3] 좌표를 선언
now_v = [2, 3]

# y축으로는 이동하지 않고, x축으로 + 1 이동 = 오른쪽으로 한 칸 이동
goto_right = [now_v[0] + dy[0] , now_v[1] + dx[0]]
# = [2, 4]

# x축으로는 이동하지 않고, y축으로 - 1 이동 = 위쪽으로 한 칸 이동
goto_up = [now_v[0] + dy[1] , now_v[1] + dx[1]]
# = [1, 3]

# y축으로는 이동하지 않고, x축으로 - 1 이동 = 왼쪽으로 한 칸 이동
goto_left = [now_v[0] + dy[2] , now_v[1] + dx[2]]
# = [2, 2]

# x축으로는 이동하지 않고, y축으로 + 1 이동 = 아래쪽으로 한 칸 이동
goto_down = [now_v[0] + dy[3] , now_v[1] + dx[3]]
# = [3, 3]

 

위와 같이, for 반복문을 통해 dx, dy의 0 ~ 3번째 인덱스를 순회하면 특정 좌표에서 상, 하, 좌, 우로 한 칸씩 움직여볼 수 있다.

 

그렇다면 어떻게 탐색을 해야하는가? 이 문제에서는 익은 토마토에서 하루가 지날 때마다 주변의 아직 익지 않은 토마토에게 영향을 주는 식이다. 마치 바이러스에 감염되는 것 처럼 주변으로 넓게 뻗어나가는 방식. 바로 너비우선탐색(BFS)를 활용해야 하는 문제이다.

 

하지만 일반적인 BFS만을 이용하면 안 된다. 최초의 익은 토마토(탐색 시작 좌표)가 하나 뿐이 아니기 때문이다. 만약 2개라면 각 두 토마토 위치에서 하루가 지날수록 각각 조금씩 영향을 퍼뜨려 나가도록 해야한다.

 

그렇다면 이 방식은 어떤가?

 

최초로 익은 토마토 좌표를 큐에 저장한다. 이후, 해당 큐를 popleft()하여 추출된 좌표 주변의 아직 익지 않은 토마토를 임시 배열에 저장한다. 여기서 임시 배열의 역할은 '주변의 익은 토마토에 의해 곧 영향을 받게 될 아직 익지 않은 토마토들'을 뜻한다.

큐의 모든 요소들을 pop하여 다음 영향을 받을 토마토들을 임시 배열에 모두 저장하면, 해당 토마토들을 큐에 모조리 저장한다. 영향을 받아 익어버렸다는 뜻이다. 이 과정을 거쳐 하루가 흘렀음을 저장한다. (여기선 day 변수에 저장한다.)

 

이런 방식을 활용하면, 하루가 지날 때마다 익은 토마토들 주변의 아직 익지 않은 토마토들에게 동시다발적으로 영향을 주는 모습을 그릴 수 있게 된다.

---

순서도

1. 입력값들을 입력받으며 토마토들이 놓여져 있는 2차원 배열 table을 세팅한다.
	해당 과정에서 익은 토마토들의 좌표를 tomato 리스트에,아직 익지 않은 최초의 토마토 개수를  no_tomato 변수에 저장한다.
    
2. 암시적 그래프에서의 BFS를 위해 익은 토마토 중심으로 상하좌우로 한 칸씩 익지 않은 토마토가 있는지 탐색하기 위해 
	dx, dy를 세팅한다.

3. 방금 갓 익은 토마토를 저장할 큐를 선언한다. ( = 방금 방문한 정점을 저장하는 것과 역할이 같다. )

4. 영향을 받아 곧 익을 예정인 토마토들의 좌표를 담을 next_v 리스트를 선언한다.

5. 큐가 최종적으로 아무것도 들어오지 않을 때까지 while문을 시작한다.
	( = 더 이상 영향을 줄 토마토가 없을 때까지 반복 )
	해당 반복문을 한 사이클 돌았다는 뜻은 하루가 지났다는 뜻을 의미할 것이다.

6. 반복문 안에 또 while문을 세팅한다. 해당 반복문 또한 큐가 빌 때까지 반복하며
	여기서 큐가 빌 때까지라는 조건은, '하루동안 영향을 받을 모든 토마토가 익을 때까지' 라는 의미이다.

7. 큐에 저장된 이미 익은 토마토들을 앞에서부터 pop하며 추출된 좌표 주변의 익지않은 토마토들을 모두 next_v에 append한다.

8. 하루동안 영향을 받은 토마토가 모두 익었다면, 안쪽 반복문을 탈출해 모든 next_v 요소들을 큐에 append한다.
	이는 다음 날 익을 예정인 토마토들을 큐에 저장한다고 생각하면 편하다.	
    그리고 익을 예정인 토마토들 개수만큼 no_tomato(익지 않은 토마토 개수)에서 차감한다.

9. 7 ~ 8 과정을 한 사이클 끝내면 day를 1 더하여 하루가 지났음을 표현한다.

10. 더 이상 영향을 줄 토마토가 없을 때까지 반복을 진행한다.

11. 결과 출력.
	만약 no_tomato가 0보다 크다면 영향을 절대 받지 못하는 토마토가 존재한다는 뜻이므로 -1을 출력,
	0이라면 day를 출력한다.

 

---

입력 예제

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

2차원 테이블 초기 세팅

주어진 입력값을 바탕으로 2차원 테이블을 세팅한다.

day의 초기값이 0인 이유는 다음과 같다.

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 한다.

전체 토마토들의 초기 상태가 곧 모든 토마토가 익은 상태라면 0을 출력해야 한다.
이는 처음 세팅되어있는 초기 세팅의 시점은 day가 0인 시점이라는 뜻이다.

 

위 흐름도대로 한 번 탐색을 진행해보자.

 

 

익은 토마토 주변의 아직 익지 않은 토마토들이 있는지 탐색을 한 단계 진행하였다. 영향을 받을 토마토들의 좌표를 next_v에 저장한다.

 

1일차 테이블 상태

영향을 받게될 모든 토마토들의 좌표를 탐색 후, 해당 좌표를 다시 큐로 옮겨준다. 하루가 지나며 영향을 받을 모든 토마토가 익었으니 day를 1 증가시킨다.

 

이 과정을 더 이상 탐색 가능한 익지 않은 토마토 좌표가 없을 때까지 반복해주면 된다.

---

 

익지 않은 주변 토마토 좌표 탐색을 진행하고, 해당 좌표들을 모두 next_v에 저장

 

2일차 테이블 상태

next_v에 탐색 가능한 모든 주변의 익지 않은 토마토 좌표를 담은 후, 해당 좌표들을 모두 큐에 저장.

---

 

3일차 테이블 상태

---

 

4일차 테이블 상태

---

5일차 테이블 상태

---

6일차 테이블 상태

---

 

탐색 종료

큐의 좌표들을 pop하여 더 이상 주변에 아직 익지 않은 토마토를 탐색할 수 없으므로 BFS를 종료한다.

모든 토마토가 익었음이 확실하니 day를 출력하고 종료한다.

 

출력 예제

6

---

주의할 점

해당 로직에서 day를 그대로 출력하면 7이 나올 것이다.

더 이상 탐색이 불가능한 상태에서 큐에 저장된 마지막 좌표들을 가지고 탐색이 가능한지 한번 더 시도해보고 반복문을 탈출하기에 마지막날에서 day가 1 더 증가하기 때문이다.

 

출력하기 전, day를 꼭 1 감소시키도록 하자.

---

전체 코드

# 7576

import sys
from collections import deque

input = sys.stdin.readline


def bfs():
    global no_tomato
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    queue = deque()

    # day : 경과 시간(단위 : 1일)
    day = 0

    # 토마토가 최초로 익은 지점을 큐에 저장
    for idx in range(len(tomato)):
        queue.append(tomato[idx])
    
    # 다음으로 토마토가 익을 예정인 토마토 좌표들을 담을 next_v 리스트
    next_v = []

    # 최종적으로 큐가 빌 때까지( 더 이상 탐색이 불가능 할 때까지 ) 반복
    while queue:
        # 다음 토마토가 익을 위치는 매 반복문 시작할 때마다 초기화
        next_v.clear()
        # 익을 예정인 토마토들은 익도록 하고, 다음 익을 예정인 토마토들을 next_v에 담는 과정
        # 익을 예정인 토마토들이 모두 익을 때까지 반복
        while queue:
            # now_v : 현재 막 익은 토마토의 좌표 정보
            now_v = queue.popleft()
            # 상하좌우에 아직 안 익은 토마토가 있는지 확인. 있다면 next_v에 append
            for i in range(4):
                if isValid(now_v, dx[i], dy[i]):
                    next_v.append([now_v[0] + dy[i], now_v[1] + dx[i]])
                    table[now_v[0] + dy[i]][now_v[1] + dx[i]] = 1
        
        # 다음에 익을 후보 토마토들을 queue에 저장
        for v in next_v:
            queue.append(v)
            # 익을 후보 토마토들 개수만큼 no_tomato 1씩 차감
            no_tomato -= 1

        # 하루 경과
        day += 1
     
    if no_tomato > 0 :
        print(-1)
    else:
        # 위의 로직대로면 더 익을 토마토가 없는 마지막 날에 하루를 또 더해버리기에 day에서 1을 차감해 출력
        print(day - 1)
        

# 상하좌우로 한 칸씩 움직일 수 있는지, 움직일 수 있다면 아직 익지 않은 토마토가 있는지 확인하는 메소드
def isValid(now_v, dx, dy):
    if 0 <= now_v[0] + dy < N and 0 <= now_v[1] + dx < M:
        if table[now_v[0] + dy][now_v[1] + dx] == 0:
            return True
        else: return False
    else:
        return False
 

if __name__ == "__main__":
    M, N = map(int, input().split())

    # 토마토 창고를 표현할 2차원 테이블 선언
    table = []

    # 익은 토마토의 위치를 담을 리스트 선언
    tomato = []
    
    # 익지 않은 토마토의 개수를 담을 no_tomato
    # 탐색이 끝나도 no_tomato가 1개 이상 남아있다면, -1을 출력하기 위함
    no_tomato = 0
    # 테이블 세팅 및 익은 토마토 위치 저장
    for row in range(N):
        _row = list(map(int, input().split()))
        table.append(_row)
        for col in range(M):
            if _row[col] == 1:
                tomato.append([row, col])
            elif _row[col] == 0:
                no_tomato += 1
    
    # 너비우선탐색 시작
    bfs()

---

풀이 후기

2개 이상의 시작점을 가진 BFS 탐색을 어떻게 진행하면 좋을까 고민하다 위의 아이디어로 훅훅 풀 수 있었던 문제였다.