백준 7576번 토마토 문제풀이, 파이썬

 

백준 7576번 : 토마토 문제풀이 [파이썬] 

---

<문제>

 

7576번 문제의 내용은 아래와 같습니다. 

 

 

토마토

 

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

8

예제 입력 2 복사

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

예제 출력 2 복사

-1

예제 입력 3 복사

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

예제 출력 3 복사

6

예제 입력 4 복사

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

예제 출력 4 복사

14

예제 입력 5 복사

2 2
1 -1
-1 1

예제 출력 5 복사

0

---

 

 

<작성한 코드>

---

 

 

<코드 풀이>

본 문제는 길찾기 문제랑 같은 메커니즘으로 접근해서 풀었다. (아래 포스팅 참고)

2023.02.01 - [백준 알고리즘] - 백준 2178번 : 미로 탐색 문제풀이, 파이썬

 

 

그래서 출력해야하는 일수를 +1씩 더해, 가장 최대값을 출력하고자했고

그 과정에서 토마토가 모두 익지 못하는 상황이면 일수가 아닌 -1을 출력해야 하기 때문에

exit()를 사용하려고했는데,,, 무슨 이유에선지 코드가 안먹어서 그냥

day1, day2로 나눠서 변수를 설정하는 방법으로 풀었다ㅠ 마음에는 안들지만

 

 

우선 BFS로 풀거기때문에 기본 세팅을 위와같이 해줬다. 

입력받은 값들을 넣어주기 위한 graph 인접행렬도 생성했다. 

 

 

bfs함수의 경우는 위와같이 정의했다.

미로찾기 문제와 같은 방식으로 상/하/좌/우를 확인해주었고

확인했을때 들어있는 토마토가 숫자 '0' 즉, 아직 익지 않은 상태라면

기존의 기준 숫자에 1을 더해주는 방식으로 일자를 세주었다. 

따로 일자를 세어주는 변수를 만들기 너무 귀찮아서,,,

 

bfs는 토마토가 익어있는 곳에서만 돌려줄거니까

graph 안에 있는 원소들을 전부 확인하면서, 

원소가 '1'인 부분을 시작지점으로 잡고, 큐에 넣어서 bfs를 돌려주었다. 

 

 

 

출력부분은 위의 내용대로 작성했다. 

우선 주석으로 달아놓은 것처럼 토마토가 모두 익지 못하는 상황이라면 -1을 출력해야하기 때문에

이중반복문으로 그래프의 값들을 전부 확인해, 익지 않은 토마토가 한개라도 있다면

day1 이라는 변수에 -1을 할당해주었다. 

 

하지만 다 확인했는데 익지 않은 토마토가 없이 다 익었다면?

day2라는 변수에 그래프에 들어가있는 최대값을 할당해준다. 

이때 애초에 시작지점은 그래프에 숫자 '1'로 들어가있기때문에

마지막에 출력할때는 day2-1을 통해 출력해주었다. 

 

그래프 탐색 문제를 여러개 풀다보니 사실 접근방법은 다들 비슷해서

생각보다 쉽게쉽게 문제를 풀어나가는 것 같다.