[백준 7576번 C/C++] 토마토

 

[백준 7576번 C/C++] 토마토

 

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

7576번: 토마토

---

 

 

해결방안

 

너비우선탐색, BFS

 

---

 

 

코드

 

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

int m, n; // m: 가로(열) 크기, n: 세로(행) 크기
vector<vector<int>> v, day; // v: 각 위치의 토마토 상태, day: 각 위치에서 토마토가 익는 데 걸리는 날짜를 저장
int totalDays; // 토마토가 모두 익을 때까지의 최소 날짜

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int startY, startX;
	cin >> m >> n;
	v.resize(n, vector<int>(m));
	day.resize(n, vector<int>(m));

	vector<pair<int, int>> startLoc; // 시작 시 익은 토마토의 위치를 저장하는 벡터

	// 각 위치의 토마토 상태를 입력받고, 익은 토마토의 위치를 startLoc에 저장.
	for(int y=0; y < n; y++){
		for (int x = 0; x < m; x++) {
			cin >> v[y][x];
			if(v[y][x]==1){ 
				startLoc.push_back({ y, x });
			}
		}
	}

	queue<pair<int, int>> Q; // 익은 토마토의 위치를 저장하는 큐
	for(int i=0; i<startLoc.size(); i++) 
	{
		Q.push({ startLoc[i].first, startLoc[i].second });// 첫 시작 시 익은 토마토의 위치를 Q에 넣음
		day[startLoc[i].first][startLoc[i].second] = 0;// 첫 시작 시 익은 토마토의 day를 0으로 설정	
	}

	while(!Q.empty())
	{
		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();

		for(int i=0; i<4; i++)
		{
			int ny = y + dirY[i];
			int nx = x + dirX[i];

			if (ny < 0 || n <= ny || nx < 0 || m <= nx || v[ny][nx] == -1) continue;

			if (v[ny][nx] == 0 && day[ny][nx] == 0) // 이동할 위치에 안 익은 토마토가 있고, 아직 방문하지 않았다면
			{
				Q.push({ ny, nx }); // 큐에 이동할 위치를 넣음
				v[ny][nx] = 1; // 토마토가 익었다고 표시
				day[ny][nx] = day[y][x] + 1;  // 이동할 위치의 day를 현재 위치의 day+1로 설정

				totalDays = max(totalDays, day[ny][nx]);
			}
		}		

		// 디버깅용
		//for (int y = 0; y < n; y++) {
		//	for (int x = 0; x < m; x++) {
		//		cout << v[y][x] << " ";
		//	}
		//	cout << "\n";
		//}
		//cout << "\n";
		//for (int y = 0; y < n; y++) {
		//	for (int x = 0; x < m; x++) {
		//		cout << day[y][x] << " ";
		//	}
		//	cout << "\n";
		//}
		//cout << "\n";
		//cout << "\n";
	}
		
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (v[y][x] == 0) // 안 익은 토마토가 하나라도 있으면
			{
				cout << "-1"; // -1을 출력하고 프로그램을 종료
				return 0;
			}
		}
	}

	cout << totalDays; // 모든 토마토가 익는 데 걸리는 최소 날짜를 출력

	return 0;
}

 

---