1. 관련 문제 🎯
문제 : 백준 7576 토마토 🍅
난이도 : 골드 5
2. 문제 소개 🧩
1️⃣ 창고에 보관하는 토마토들 중에 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.
- 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않은 칸이다.
2️⃣ 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
- 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.
3️⃣ 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
4️⃣ 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
3. 문제 풀이 🖌️
3-1. 창고에 보관하는 토마토들의 정보를 입력받는다.
- 익은 토마토(tomato[j][i] == 1)의 위치 정보를 'wellTomato'에 저장해준다.
- 익지 않은 토마토(tomato[j][i] == 0)의 개수를 센다.
vector<pair<int,int>> wellTomato; //익은 토마토 자리 칸
int zeroTomato = 0; //익지 않은 토마토 개수
for (int i = 0; i < n; i++) {
for(int j = 0; j < m; j++){
//1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토가 들어있지 않은 칸
cin >> tomato[j][i];
if(tomato[j][i] == 1){
wellTomato.push_back({j,i});
}
else if(tomato[j][i] == 0){
zeroTomato++;
}
}
}3-2. 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력한다.
- 익지 않은 토마토의 개수가 0인 경우, 0을 출력한다.
if(zeroTomato == 0){
cout<<0<<"\n"; //저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력
return 0;
}3-3. 초기에 익은 토마토 정보를 que에 넣어준다.
- 초기에 익은 토마토가 여러 군데에 있을 수 있다!
그러므로 익은 토마토를 root(depth = 0)라고 생각하고, 여러 개의 그래프를 생성해주기 위해서 que에 root 노드를 넣어준다.
queue<pair<pair<int,int>,int>> que; //위치 x, 위치 y, 깊이
for(auto i : wellTomato){
que.push({{i.first, i.second}, 0});
}
3-4. BFS를 사용하여 익은 토마토들에 인접한 익지 않은 토마토들을 익힌다.
- 하루 후에 익은 토마토와 인접한 모든 익지 않은 토마토들이 익기 때문에 그래프에서 같은 깊이인 토마토들은 모두 익는다. 따라서 같은 깊이를 살펴보는 BFS를 사용했다.
- 만약 DFS를 사용한다면, 하루 후에익은 토마토와 인접한 토마토들 중에서 하나만 익히기 때문에 해당 문제에서는 BFS가 더 적절하다!!
- 하루마다 root 토마토에서 depth가 1씩 증가하면서 토마토가 익는다.
따라서, root에서부터의 depth가 해당 토마토가 익은 날이다. - 인접한 토마토는 익은 토마토의 상하좌우에 있다.
따라서, x+dx[i]와 y+dy[i]로 상하좌우 중에서 익지 않은 토마토가 있는지를 살펴본다. 익지 않은 토마토는 익히고 나서 depth+1을 한 값과 위치 정보를 que에 넣어서 BFS를 진행한다.
while (!que.empty())
{
int x = que.front().first.first;
int y = que.front().first.second;
int depth = que.front().second;
que.pop();
ans = max(ans, depth);
for(int i=0; i<4; i++){
int X = x+dx[i]; int Y = y+dy[i];
if(X>=m or X<0 or Y>=n or Y<0) continue;
if(tomato[X][Y] == 1 or tomato[X][Y] == -1) continue;
tomato[X][Y] = 1;
cnt++;
que.push({{X,Y},depth+1});
}
}3-5. 토마토가 모두 익으면 답을 출력한다.
- 토마토가 모두 익지는 못하는 상황이면 -1을 출력한다.
if(cnt == zeroTomato) cout<<ans<<"\n";
else cout<<-1<<"\n"; //토마토가 모두 익지는 못하는 상황이면 -14. 전체 코드 🔑
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int m, n; //상자의 가로 칸의 수, 상자의 세로 칸의 수
int tomato[1001][1001];
int dx[4] = {0,1,-1,0};
int dy[4] = {1,0,0,-1};
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> m >> n;
vector<pair<int,int>> wellTomato; //익은 토마토 자리 칸
int zeroTomato = 0; //익지 않은 토마토 개수
for (int i = 0; i < n; i++) {
for(int j = 0; j < m; j++){
//1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토가 들어있지 않은 칸
cin >> tomato[j][i];
if(tomato[j][i] == 1){
wellTomato.push_back({j,i});
}
else if(tomato[j][i] == 0){
zeroTomato++;
}
}
}
if(zeroTomato == 0){
cout<<0<<"\n"; //저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력
return 0;
}
queue<pair<pair<int,int>,int>> que; //위치 x, 위치 y, 깊이
for(auto i : wellTomato){
que.push({{i.first, i.second}, 0});
}
int ans = 0;
int cnt = 0; //익은 토마토 개수
while (!que.empty())
{
int x = que.front().first.first;
int y = que.front().first.second;
int depth = que.front().second;
que.pop();
ans = max(ans, depth);
for(int i=0; i<4; i++){
int X = x+dx[i]; int Y = y+dy[i];
if(X>=m or X<0 or Y>=n or Y<0) continue;
if(tomato[X][Y] == 1 or tomato[X][Y] == -1) continue;
tomato[X][Y] = 1;
cnt++;
que.push({{X,Y},depth+1});
}
}
if(cnt == zeroTomato) cout<<ans<<"\n";
else cout<<-1<<"\n"; //토마토가 모두 익지는 못하는 상황이면 -1
}5. 결과 🏆
컴퓨터공학과 학생이며, 백엔드 개발자입니다🐰