문제 정보
백준 ( BOJ ) 7576 토마토
문제 풀이 : bfs
문제 출처 : https://www.acmicpc.net/problem/7576
시작 Thinking
bfs이긴 bfs인데, 이렇게 몇일이 걸렸는지? 가 필요한 문제에서는 두가지 방법이 있습니다.
첫번째는 큐로 넘길때, 몇일째인지 같이 넘기는 겁니다.
예를들면 (1,1)을 1일째에 넘긴다면,
{(1,1),1}
이런식으로요.
아니면, 아예 쌍둥이 큐를 만들어서, 데이터큐 날짜큐 (1,1) / 1
이런식으로 같이 움직이도록 만들어 줘도 됩니다.
원래는 이렇게 자주 했는데,
이번에는 두번쨰 방법인 재귀를 사용해서 해보도록 하겠습니다.
우선 기본 틀은 똑같으니, 무엇이 다른지만 보고 가도록 하겠습니다.
bfs()
n = 큐 갯수
for(int i =0 ; i < n; i++){
do
}
if( 큐 not empty)
bfs()
}
}
바로 재귀를 돌리돼, 큐에 들어와 있는 횟수만큼은
다 처리하면서, 큐에 새로이 넣어 주는 방식입니다.
뭐 두방법중 어떤걸 선택하셔도 상관은 없습니다~.
아 그리고 이렇게, 완성하지 못하는 경우의 수가 있다면,
미리 완성되려면 남은 수를 정해놓고 돌리면 됩니다.
이 문제 같은 경우에는, 익지 않은 토마토 갯수가 되겠죠.
뭐, 다 끝나고 한번에 검사하는것도 크게 상관 없습니다 .
이문제는 다 끝나고 나서 체크해도 되니까요.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int notyet = 0;
int done = 0;
int day = 0;
vector<vector<int>> tomato;
queue<pair<int,int>> newOne;
bool checkOk(int i, int j) {
if (i < 0 || i >= n)
return false;
if (j < 0 || j >= m)
return false;
return true;
}
void plust(int i, int j) {
i--;
if( checkOk(i,j) && tomato[i ][j] == 0){
tomato[i][j] = 1;
newOne.push(make_pair(i, j));
notyet--;
}
i += 2;
if (checkOk(i, j) && tomato[i][j] == 0) {
tomato[i][j] = 1;
newOne.push(make_pair(i, j));
notyet--;
}
i--;
j--;
if (checkOk(i, j) && tomato[i][j] == 0) {
tomato[i][j] = 1;
newOne.push(make_pair(i, j));
notyet--;
}
j += 2;
if (checkOk(i, j) && tomato[i][j] == 0) {
tomato[i][j] = 1;
newOne.push(make_pair(i, j));
notyet--;
}
}
void bfs() {
int tx, ty;
done = newOne.size();
for (int i = 0; i < done; i++) {
tx = newOne.front().first;
ty = newOne.front().second;
newOne.pop();
plust(tx, ty);
}
day++;
if (!newOne.empty()) {
bfs();
}
}
int main() {
int temp;
cin >> m >> n;
tomato.assign(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> temp;
tomato[i][j] = temp;
if (temp == 0)
notyet ++;
else if (temp == 1) {
newOne.push(make_pair(i, j));
}
}
}
bfs();
if (notyet != 0)
cout << -1;
else
cout << day-1;
}