[BOJ] 7576번 : 토마토

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second 
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int days[1005][1005]; 
int board[1005][1005]; 
int rows, cols; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int>> Q; 
	cin >> cols >> rows; 
	// board에 값 입력받기 
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) Q.push({ i,j });
			if (board[i][j] == 0) days[i][j] = -1;
		}
	}



	// Queue가 empty하기전까지 실행 
	while (!Q.empty()) {
		pair<int, int> current = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 4; dir++) {
			int nx = current.X + dx[dir];
			int ny = current.Y + dy[dir];
			if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue; 
			if (board[nx][ny] != 0 || days[nx][ny] != -1) continue;
			days[nx][ny] = 1 + days[current.X][current.Y];
			Q.push({ nx,ny });
		}
	}

	
	// max값 추출
	int maxDays = -1;
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (days[i][j] == -1 && board[i][j] == 0) {
				cout << -1 << '\n';
				return 0;
			}
			maxDays = max(maxDays, days[i][j]);
		}
	}
	cout << maxDays << '\n';
	return 0;
}

이 코드는 chatgpt 4o한테 도움을 받았다. 나는 기존에 모든 1을 다 Queue에 넣지 않고, 하나씩 넣어서, 넓혀나가는 과정을 생각하고 코드를 작성했다. 하지만, 답이 나오지 않았다. 이점을 개선한 코드는 1을 모두 Queue에 넣어놓고 출발한다. 외우자.