https://jdselectron.tistory.com/55
를 참고했다. tomato struct 를 정의할 때 int x,y; 순으로 적으니 답이 제대로 나오지 않았다.
y,x 로 수정해야했음. 왜일까??
#include <queue>
#include <iostream>
#include <stdio.h> // use printf, scanf
#include <cstring> // use memset
#define MAX_SIZE 1000 + 1
using namespace std;
int M, N; //M:가로칸 수 N:세로칸 수
struct tomato {
int y,x;
};
queue<tomato> q;
//int dx[4] = { -1,0,1,0 };
//int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0 , -1 };
int n, m, result = 0;
int graph[MAX_SIZE][MAX_SIZE];
bool IsInside(int ny, int nx) {
return (0 <= nx && 0 <= ny && nx < M&& ny < N);
}
void bfs(void) {
while (!q.empty()) {
// 큐의 현재 원소(익은 토마토(1))를 꺼내기
int y = q.front().y;
int x = q.front().x;
q.pop();
// 해당 위치의 주변을 확인
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
// 지도를 벗어나지 않고, 익지않은 토마토(0)라면
if (IsInside(ny, nx) == 1 && graph[ny][nx] == 0) {
graph[ny][nx] = graph[y][x] + 1;
q.push({ ny, nx });
}
}
}
}
int main()
{
/* 토마토 농장(그래프)의 크기 입력 (가로/세로)*/
scanf("%d %d", &M, &N);
/* 그래프 정보 입력*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == 1) { // 익은토마토(1) -> 큐
q.push({ i, j });
}
}
}
//cin >> M >> N;
//for (int i = 0; i < N; i++)
//{
// for (int j = 0; j < M; j++)
// {
// cin >> graph[i][j];
// cout << graph[i][j] << endl;
// if (graph[i][j] == 1)
// {
// q.push({ i,j });
// }
// }
//}
bfs();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (graph[i][j] == 0)
{
cout << "-1";
return 0;
}
if (result < graph[i][j])
{
result = graph[i][j];
}
}
}
printf("%d\n", result - 1);
return 0;
}