백준 - 7576번 토마토

문제

하루마다 익은 토마토가 상하좌우의 토마토를 익게만든다
며칠이면 토마토가 모두 익나?

생각

최소 며칠 후 모든 토마토가 익는지 구하는 문제이므로 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;
}