[알고리즘 일기 - 파이썬] 171. 토마토

문제 171. (2022-02-01)

 

7569번: 토마토

Baekjoon 7569. 토마토

[파이썬(python) 풀이]

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

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

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

 

---

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

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

 

---

출력

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

 

---

입력 예시

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

 

---

출력 예시

-1

 

---

❧ 정답

 

 

🔎IDEA) 단계별로 bfs를 진행한 뒤 그 단계의 진행 횟수를 세야한다.

• tom : 익은 토마토들의 좌표를 담는 리스트
• tomatos : 상자의 상태를 담는 리스트
• zeros_cnt : 안익은 토마토들의 개수 (추후 turn 과 그 값 비교 위함)
• cnt : 토마토가 다 익을 때까지 걸리는 시간(단계)
• turn : 토마토를 총 익힌 횟수
• queue : 이전 단계에서 새롭게 익은 토마토들의 좌표값
• queue_list: 현재 단계에서 방문 처리를 할 토마토들의 좌표값

 

[Line 10 - 12]
👉 가로, 세로, 높이의 3차원 공간에 토마토의 위치를 표현해야하므로 x, y, z의 세 위치 벡터를 사용한다.

 

[Line 15 - 24]
👉 상자에 담긴 토마토의 위치를 입력을 통해 받아서 리스트에 저장한다.

• 안익은 토마토가 있으면 flag 값을 '1'로 바꿔준다.
• 익은 토마토들의 좌표값을 tom 리스트에 담는다.
• 익지 않은 토마토의 개수를 세서 zeros_cnt 에 그 값을 담는다. (이후 bfs에서 토마토를 몇 번 익혔는지 그 횟수를 비교하기 위함)

 

[Line 27 - 55]
👉 익은 토마토들(tom)의 좌표값을 큐에 삽입한다.
👉 queue_list 에 queue에 담았던 익은 토마토들의 좌표값을 삽입한다.
👉 익은 토마토들을 모두 방문한 뒤 인근 토마토들을 탐색하며 안익은 토마토가 있을 경우

1. 큐에 해당 좌표값을 추가한다.
2. 해당 토마토를 익게 한다.(1로 처리)
3. turn의 값을 1 올린다.

👉 for문을 모두 돌고 나서는 인근 토마토들을 모두 방문한 뒤 안익은 토마토를 익힌 상태이므로 cnt의 값을 '1' 올려준다.
👉 그렇게 모든 토마토들을 다 익히면 반복문을 종료한다.
(맨 처음에 안익은 토마토의 개수를 센 zeros_cnt와 토마토를 익힌 횟수를 담은 turn의 값이 같을 경우)

 

[Line 59 - 65]
👉 bfs로 인근 노드 탐색 후, 만약 안익은 토마토가 있을 경우, tomatos[i][j][k] == 0
'-1'을 출력하고 프로그램을 종료한다.

 

[Line 66 - 69]
👉 Line 20에서 안익은 토마토가 있을 경우 flag값을 1로 바꿔줬기때문에, 안익은 토마토가 하나도 없을 경우(맨 처음부터 모든 토마토가 익은 상태)이면 '0'을 출력한다.

 

🌟 queue와 queue_list의 역할 비교

• queue : 단계 한번 당 익힘도를 확산 시켜야 할 토마토의 좌표값을 담고 있다.
• queue_list : 각 단계에서 방문처리를 위한 반복문을 수행하기 위해 queue의 익은 토마토의 좌표값을 담는다.