(백준 7576번 토마토 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 7

백준 7576번

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

#include <iostream>
#include <queue>
using namespace std;

class tomato {
public:
	int N, M; 
	vector<vector<int>> arr;
	queue<pair<int, int>> Q;
	int dir_x[4] = { 0, -1, 1, 0 };
	int dir_y[4] = { 1, 0, 0, -1 };

	tomato(int M, int N) : M(M), N(N) {
		arr.resize(N);
		for (int i = 0; i < N; i++) {
			arr[i].resize(M);
		}
	}

	void getInfo() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> arr[i][j];
				if (arr[i][j] == 1) Q.push(make_pair(i, j));
			}
		}
	}

	bool isRipened(){
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0) return false;
			}
		}
		return true;
	}
	bool isInside(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= M) return false;
		return true;
	}

	void bfs() {
		cout << bfs(0, 0);
		return;
	}

private:
	int bfs(int x, int y){
		// 익은 과일이 없다면 return -1
		if (Q.empty()) return -1;
		// 모든 과일이 모두 익었다면 return 0
		if (isRipened()) return 0;

		int level = 0; 
		while (!Q.empty()) {
			cout << "level : " << level << endl;
			int qsize = Q.size();

			for (int i = 0; i < qsize; i++) {
				int currX = Q.front().first;
				int currY = Q.front().second;
				Q.pop();

				for (int j = 0; j < 4; j++) {
					int nextX = currX + dir_x[j];
					int nextY = currY + dir_y[j];

					if (isInside(nextX, nextY) && arr[nextX][nextY] == 0) {
						arr[nextX][nextY] = 1;
						Q.push(make_pair(nextX, nextY));
						cout << "nextX: " << nextX << "nextY" << nextY << endl;
					}

				}
			}
			level++;
		}
		if (isRipened()) return level-1;
		return -1;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int M, N; cin >> M >> N;
	tomato t(M, N);
	t.getInfo();
	t.bfs();
	return 0;
}

 

처음에는 크기가 1001*1001인 int array를 지정해서 문제를 풀었는데

stack에 너무 많은 자리를 차지한다는 경고문구가 떴다.

 

오,, 심박한 경고문,,

 

그래서 int 2차원 배열 대신 vector를 사용해서 풀었다.

bfs 살짝 감 잡은거 같아서 신난다ㅎㅎ