문제
하루마다 익은 토마토가 상하좌우의 토마토를 익게만든다
며칠이면 토마토가 모두 익나?
생각
최소 며칠 후 모든 토마토가 익는지 구하는 문제이므로 BFS이다!
시간 초과 아이디어 1
익은 토마토 위치 큐에 넣어주고, while돌면서 큐 값 빼서 주변 익게 하고,
그 큐를 다 비우면, day++ 하는 방법을 처음엔 생각했다
day++을 따로 빼내는 것이 아 날짜가 지났구나! 이해하기도 쉽고,
큐에 지금이 며칠째인지 저장을 따로 안 해두 괜찮으니 좋을 것이라고.. 생각했었음..
bool spread() {
bool flag = false;
pair<int, int> temp;
//돌면서 1인 애 다 찾아 큐에 넣고
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j] == 1) {
q.push(make_pair(i, j));
}
}
}
//큐에 있는 애들 다 처리해주자!
while (!q.empty()) {
temp = q.front();
if (flag == true) {
ripe(temp.first, temp.second);
}
else {
flag = ripe(temp.first, temp.second);
}
q.pop();
}
return flag;
}
int main() {
//////
while (1) {
//그 전 상태를 저장해서 비교하는 건 너무 복사하는 데 시간걸릴듯
//변경이 안 됌 == 더이상 할 것 엑스
if (spread() == false) {
break;
}
else {
day++;
}
}
//////
return 0;
}나름 끝내는 것도 고민할 때 흐음.. 바로 전 상태랑 비교하는 건 힘들까봐
한 번 퍼질 때 변화가 있는지 없는지를 반환하게 했었음
시간 초과 아이디어 2
위에 코드로 하면 날짜도 잘 측정하구 좋은뎅,, 시간초과가 걸렸따
1인 애들을 다 찾아서 큐에 넣어주는 게 조금 멍청했던 것 같아서
bool spread() {
//////
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j] == 1) {
q.push(make_pair(i, j));
//시간초과뜬다! 2로 만들어주자 이미 퍼진애는!
state[i][j] = 2;
}
}
}
///////
}한 번 퍼진곳은 state 값을 2로 만들어서 다시보지 않도록 했지만 여전히 시간초과..
수정 후
그냥 날짜 지나고 계속 퍼지려고 할 때마다 맵에서 1 찾아주는게 너무 힘든거였어..
아무리 2로 바꾸고 해봐두 그냥 탐색한다는 거 자체가 부담이였던거지 멍청이이ㅣ2222
맨 처음에만 1 찾아서 큐에 넣고,
큐는 며칠째 생각한다기 보단 그냥 빌 때까지!!! 계속 넣고 빼고 넣고 빼고 ~
며칠째인지는 큐에 같이 넣고 다닌다~~ 로 변경
(+ 이 문제를 풀면서 조금 BFS를 이해한 듯
단순히 큐를 이럴때 저럴때 쓴다기보단 계속 물흐르듯이 번져??나가게!)
(++ 하루 하루 번진게 변화있는지 보는 작업도 안 해두대!! 그냥 큐 빌때까지니까)
void spread() {
pair<int, pair<int, int>> temp;
//맨 처음 한 번만 돌면서 1인 애 다 찾아 큐에 넣고
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j] == 1) {
q.push(make_pair(0, make_pair(i, j)));
}
}
}
//큐에 있는 애들 다 처리해주자!
while (1) {
temp = q.front();
ripe(temp.first, temp.second);
q.pop();
if (q.empty()) {
if (allRipe()) {
cout << temp.first;
}
else {
cout << "-1";
}
break;
}
}
}이렇게 함수 짜고, 메인 함수에서는 얘 한 번만 호출하게한당
예전에 완전 멍청이였어서 글 쓴당~~ (근데 다시 코드짜려고 해도 또 멍청해!!)
코드
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m, n;
int state[1000][1000];
queue<pair<int, pair<int, int>>> q;
bool allRipe() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j] == 0) {
return false;
}
}
}
return true;
}
void ripe(int count, pair<int, int> p) {
//p.first p.second로 계속 코드 써나가면 복잡하니까 쉽게 변수로 표현
int row = p.first;
int col = p.second;
if (row - 1 >= 0 && state[row - 1][col] == 0) {
q.push(make_pair(count + 1, make_pair(row - 1, col)));
state[row - 1][col] = 1;
}
if (row + 1 < n && state[row + 1][col] == 0) {
q.push(make_pair(count + 1, make_pair(row + 1, col)));
state[row + 1][col] = 1;
}
if (col - 1 >= 0 && state[row][col - 1] == 0) {
q.push(make_pair(count + 1, make_pair(row, col - 1)));
state[row][col - 1] = 1;
}
if (col + 1 < m && state[row][col + 1] == 0) {
q.push(make_pair(count + 1, make_pair(row, col + 1)));
state[row][col + 1] = 1;
}
}
void spread() {
pair<int, pair<int, int>> temp;
//맨 처음 한 번만 돌면서 1인 애 다 찾아 큐에 넣고
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j] == 1) {
q.push(make_pair(0, make_pair(i, j)));
}
}
}
//큐에 있는 애들 다 처리해주자!
while (1) {
temp = q.front();
ripe(temp.first, temp.second);
q.pop();
if (q.empty()) {
if (allRipe()) {
cout << temp.first;
//큐에서 맨 마지막에 처리한게 마지막 날짜니까 출력
}
else {
cout << "-1";
}
break;
}
}
}
int main() {
cin >> m;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> state[i][j];
}
}
spread();
return 0;
}