[백준] #7576 토마토 c++

Hyeju·2022년 11월 3일
0

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;

}

0개의 댓글