[Baekjoon] 7576 토마토

ThumbNail

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

7576번: 토마토

문제

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

m * n 격자

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

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

 

입력

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

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

출력

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

---

예시 입력과 출력은 다음과 같다.

 

---

여기서 필자가 제일 먼저 본 예제는 1.이다.

예제 1.에서 생각해 보면, 

여기서

이렇게 바뀌고

이렇게 바뀌어간다.(익어간다.)

 

이렇게 보았을 때, 1인 칸 주변의 칸들이 먼저 1로 변하고, 또 그 주변 칸이 1로 변한다는 점에서

bfs로 해결이 가능하다는 점을 유추할 수 있다.

 

참고) bfs와 dfs는 각각 queue와 stack 자료구조를 이용하여 구현할 수 있으며, 그림으로 보면 다음과 같다.

bfs와 dfs 예시 사진

왼쪽이 dfs, 오른쪽이 bfs이다.

dfs는 Depth-First-Search의 약자로, 일단 깊게 내려간 다음, 끝을 찍고 이전 노드의 다른 자식 노드를 탐색하는 방식이다.

bfs는 Breadth-First-Search의 약자로, 그 노드의 자식 노드부터 전부 탐색한 다음, 다음 줄의 자식 노드를 탐색한다.

 

여기서 가까이 있는 노드들부터 방문한다는 점에서 이 문제가 bfs와 연관되어 있다는 점을 알 수 있다.

 

따라서 이를 구현한 알고리즘에는 bfs가 쓰이며 전반적인 아이디어는 다음과 같다. 

 

1. m, n값을 입력받는다.
2. 다음 n개 줄에서 토마토가 들어 있는 칸의 입력을 받는다.
3. queue를 만들고, 현재 칸을 한번 돌면서 1인 칸의 좌표를 queue에 추가한다.
4. delay 변수에 현재 queue의 길이만큼을 저장한다.
5. while(queue) : {    (queue에 값이 있는 한 반복한다)
6. temp에 queue에 있는 값 한 개를 뺀다. (현재 위치를 저장)
7. delay값을 1 줄인다.
8. lst[현재위치]의 값을 1로 변경한다.
9. 만약 lst[현재위치]의 상, 하, 좌, 우에 0이 있다면 queue에 추가한다.
10. 만약 delay값이 0이라면 cnt를 1 증가시키고 delay에 queue의 길이만큼을 다시 할당한다.
}
11. lst를 돌며 0이 있는지 찾는다. 만약 0이 있다면 succcess에 -1을 대입한다.
12. 만약 success가 -1이라면 -1을 출력한다.
아니라면 cnt - 1값을 출력한다.

여기서 delay변수의 의미는 다음 줄 노드의 개수를 저장한다.

만약 while문을 한 번 반복할 때마다 cnt값을 1 증가시킨다면 그 수는 전체 노드의 개수만큼 이 될 것이다.

그래서 delay값에 그 줄의 노드 개수만큼의 값을 대입해 그 만큼 counting을 하지 않도록 해서

전체 bfs시 tree에서 몇 줄이 나오는지를 알아본다.

 

이 문제를 풀며 어려웠던 점은

1. 좌표가 lst[temp[0]][temp[1]]로 표현되어서 x, y 좌표가 헷갈렸음

2. queue에 들어간 값이 또 들어가지 않도록 하기 위해 queue_chk값을 새로 만들어, 이미 방문한 노드를 표시해줘야 했음. 기존 방식은 queue에 그 값이 있는지 반복하며 검사하는 방식, O(k). 이걸로 시간 초과 많이 걸렸음.

3. delay값을 언제 감소시키고 언제 0인지를 검사해서 cnt 값을 증가시킬지 애매했음.

사실 이 점이 가장 어려웠던 게, 처음에 1인 노드부터 시작해서 마지막에 총 cnt를 출력할 때 1을 빼 주어야 하는데, 이를 하다 보니 많이 헷갈렸다.

결국 처음 temp에 queue값을 하나 뺄 때 delay를 1 감소시키고, queue에 값 추가가 끝난 다음 delay값을 검사하는 코드로 완성했다.

 

전체적인 코드는 다음과 같다.

# 7576 토마토_ver.2
import sys
from collections import deque
m, n = map(int, sys.stdin.readline().split())
lst = []
success = 0
cnt = 0
delay = 0
for i in range(n):
    lst.append(list(map(int, sys.stdin.readline().split())))

queue = deque()
queue_chk = [[0 for j in range(m)]for i in range(n)]

for i in range(n):
    for j in range(m):
        if lst[i][j] == 1 and queue_chk[i][j] == 0:
            queue.append((i, j))
            queue_chk[i][j] = 1

delay = len(queue)
while queue:
    temp = queue.popleft()
    delay -= 1
    
    lst[temp[0]][temp[1]] = 1
    if temp[0] > 0 and lst[temp[0]-1][temp[1]] == 0 and queue_chk[temp[0]-1][temp[1]] == 0:
        queue.append((temp[0]-1, temp[1]))
        queue_chk[temp[0]-1][temp[1]] = 1
    if temp[1] > 0 and lst[temp[0]][temp[1]-1] == 0 and queue_chk[temp[0]][temp[1]-1] == 0:
        queue.append((temp[0], temp[1]-1))
        queue_chk[temp[0]][temp[1]-1] = 1
    if temp[0] < n-1 and lst[temp[0]+1][temp[1]] == 0 and queue_chk[temp[0]+1][temp[1]] == 0:
        queue.append((temp[0]+1, temp[1]))
        queue_chk[temp[0]+1][temp[1]] = 1
    if temp[1] < m-1 and lst[temp[0]][temp[1]+1] == 0 and queue_chk[temp[0]][temp[1]+1] == 0:
        queue.append((temp[0], temp[1]+1))
        queue_chk[temp[0]][temp[1]+1] = 1
    
    if delay == 0:
        cnt += 1
        delay = len(queue)

for i in range(n):
    if 0 in lst[i]:
        success = -1
        break
    
if success == -1:
    print(-1)
else:
    print(cnt-1)

 

약간 1인 노드로부터 1이 퍼져나가는 느낌으로 총 몇 번 시행되어야 1이 판을 전부 뒤덮는지 알아내는 느낌이다.

만약 queue에 들어갈 수 있는 값이 더 이상 없는데(1 주변에 있는 0만 1이 될 수 있음)

0이 아직 판에 남아 있다면, 그 판은 끝낼 수 없는 판이라고 판단하고 -1을 출력한다.