[ C++ ] #7576 토마토

 

 

골드단계의 문제를 스스로 풀어보는건 처음이라! 꼭 스스로 풀겠다는 다짐을 하며 문제를 보았다.

 

음..1부터 시작해서 그냥 0인거 BFS하면 되겠다 싶었는데

요일를 세야하니까 한 타임에 몇개가 큐에 들어왔는지 세서

그 큐가 다 소진될때마다 하루씩 늘려야겠다고 생각했다.

 

풀 수 있을거같은데 시간초과가 날거같은...느낌? 일단 GO

---

다른 방법이 생각났다.

며칠째에 내가 익었는지 내 칸에 적어놓는다면

내 다음칸은 내 칸을 보고 +1을 하면 된다!!

다이나믹한 방법이다.

 

야호~! 맞았따~!~!

혼자힘으로 했다는게 너무 뿌듯하다~!~!

 

#include<iostream>
#include<queue>
#include<vector>


using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = { 1,0,-1,0 };
queue<pair<int, int>> Q;
int tomato[1000][1000];
int check[1000][1000];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int num = 0, day = 0, n, m;

	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {  //익은 토마토가 있다면 방문
				Q.push({ i,j }); check[i][j] = 1;
			}
		}
	}
    
	pair<int, int> C;


	while(!Q.empty()) {

		C= Q.front();
		Q.pop();
		

		for (int i = 0; i < 4; i++) {
			int nx = C.first+dx[i];
			int ny = C.second+dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if(tomato[nx][ny]!=0||check[nx][ny]!=0) continue;

			tomato[nx][ny] = 1; //익었다고 표시
			check[nx][ny] = check[C.first][C.second]+1; //하루 지난 날짜 표시
			Q.push({ nx,ny });
		}
	}

	for (int i = 0; i < n; i++) { //모든 과정을 거쳤는데도 안익은게 있다면 -1
		for (int j = 0; j < m; j++) {
			if (tomato[i][j] == 0) {
				cout << -1; return 0;
			}
		}
	}

	cout << check[C.first][C.second]-1;   //0번째날을 1로 설정해서 하루빼주기
	return 0;

}