백준 7576 토마토

이제 방학이 되었으니 다시 알고리즘을 조금씩 해야하지 않을까 싶어서 다시 시작

알고리즘이랑 안드로이드랑 병행해서 공부 중임

백준 7576 : 토마토

이 문제는 BFS 문제인게 뻔히 보인다.

다만 탐색을 할때 

다음 탐색되는 노드의 레벨이 원래 계산되어 있던 레벨보다 더 좋은 레벨이면 갱신을 해줘야 한다.

#define INT_MAX_ 2147480000
#include 
#include 
#include 
#include 

using namespace std;

int M, N;

int day;
int max_day = 0;
int box[1001][1001];
pair normalTomato[1000001];
int normalTomatoSize = 0;
int date[1001][1001];


int main() {
	ifstream inFile("output.txt");
	cin >> M >> N;

	int di[4] = {-1, 0, 1, 0};
	int dj[4] = {0, +1, 0, -1};

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			date[i][j] = INT_MAX_;
			cin >> box[i][j];
			if (box[i][j] == 1) {
				normalTomato[normalTomatoSize] = make_pair(i, j);
				normalTomatoSize++;
				date[i][j] = 0;
			}

		}
	}
	queue> bfs;
	for (int i = 0; i < normalTomatoSize; i++) {
		//day = 0;
		bfs.push(normalTomato[i]);
		bfs.push(make_pair(-1, -1));
		while ( true ) {
			int now_i = bfs.front().first;
			int now_j = bfs.front().second;
			int now_date = date[now_i][now_j];
			if (now_i == -1) {
				bfs.pop();
				if (bfs.empty()) break;
				bfs.push(make_pair(-1, -1));
				continue;
			}

			for (int k = 0; k < 4; k++) {
				int next_i = now_i + di[k];
				int next_j = now_j + dj[k];
				if (next_i >= 0 && next_i < N && next_j >= 0 && next_j < M) {
					if (box[next_i][next_j] == 0 || (date[next_i][next_j] > date[now_i][now_j] + 1 && box[next_i][next_j] == 1)) {
						bfs.push(make_pair(next_i, next_j));
						box[next_i][next_j] = 1;
						date[next_i][next_j] = date[now_i][now_j] + 1;
					}
				}
			}
			bfs.pop();
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (box[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			if (date[i][j] >= max_day && box[i][j] == 1) {
				max_day = date[i][j];
			}
		}
	}
	cout << max_day << endl;

	return 0;
}

normalTomato는 시작하자마자 익어있는 토마토들이다

이 토마토를 루트로 하여 BFS탐색을 하는데,

이때 익은 토마토의 앞뒤좌우의 토마토가 익지 않아있을 경우를 토마토끼리 연결되어있다! 라는 개념으로 BFS탐색을 한다.

그리고 위에 말했던 것 처럼, BFS탐색시, 이미 탐색된 노드(이미 익어버린 토마토)를 방문했는데 

이 노드의 레벨(date)보다 지금 내가 가지고 있는 date +1가 더 낮은 숫자라면(즉, 더 빨리 익게 할수 있는 루트가 있다면),

이 노드의 date를 갱신하고 큐에 또 넣는다.

이 문제를 풀때 초반에 메모리 초과가 났는데

while루프 초반에 노드를 방문했다고 표시를 해버리는 바람에 큐에 엄청난 노드들이 중복해서 들어가서 그랬었다.

box[next_i][next_j]를 1로 바꾸는 코드를 

[노드 방문 후] 에서 [노드 방문 전] 으로 바꾸어 해결

멍청했다..