[ 백준 7576] 토마토 (C++)

7576번: 토마토

 

문제!

---

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

---

익은 토마토옆에 있는 일반토마토가 하루만에 익는다고 생각했을때 모두 익게되는 기간을 구하는 문제로

일반적인 탐색문제였습니다!

 

 

이제 어떻게 탐색해야 하느냐... 하는건데

dfs,bfs탐색 둘다 가능해 보이네요

 

일단 bfs로 풀어 보았습니다.

 

 

시작!

---

먼저 기본적인 것들을 선언해 줍시다!

int M = 0, N = 0;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 }; // 우 좌 상 하

vector<vector<int>>grap(1010, vector<int>(1010, -1)); // 맵그래프!
queue<pair<int,int>>start_p; // bfs탐색을 위한 지점저장큐

 

저는 전체를 -1로 선언해주고 tomato가 0일때는 0으로 , 1일때는 1로 변환시켜주었습니다!

 

그러면 대충 아래와 같은 모양이 되고 

-1-1-1-1-1-1-1 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 0 0 1 -1
-1-1-1-1-1-1-1 -1

이렇게 되면 범위를 넘어가는지는 확인 x , -1인지만 확인해주면 되게됩니다!

 

 

위의 상태가 되도록 입력을 받아주고 시작지점들을 큐에 모아줍시다.

for (int i = 1; i < N+1; i++) { // 1~N까지
		for (int j = 1; j < M+1; j++) {
			cin >> tomato;
			if (tomato == 0) {
				grap[i][j] = tomato;
			}

			if (tomato == 1) {
				grap[i][j] = tomato;
				start_p.push({ i,j });
			}
		}
	}

 

 

다음은 bfs탐색입니다! 

현재칸이 0 인지만 확인해줍시다.

void find() { // 

	while (start_p.size() != 0) {
		pair<int, int>memo;
		memo = start_p.front();
		start_p.pop();

		int y = memo.first;
		int x = memo.second;

		
		for (int i = 0; i < 4; i++) {
			
			if (grap[y+dy[i]][x + dx[i]] == 0) {
				start_p.push({ y + dy[i] ,x + dx[i] });
				grap[y + dy[i]][x + dx[i]] = grap[y][x]+1;
			}
		}
		
	}

}

그리고 각 칸에는 전칸의 값+1씩 더해주어 며칠이 걸리는지 구해줍시다.

 

 

마지막으로 그래프에서 최댓값 일수를 구해주면서 안익은 토마토가 있으면 -1을 출력해줍시다.

int max = 0;

	for (int i = 1; i < N + 1; i++) { // 며칠만에?
		for (int j = 1; j < M + 1; j++) {
			if (grap[i][j] == 0) {
				cout << -1;
				return 0;
			}

			if (grap[i][j] > max) {
				max = grap[i][j];
			}
		}
		
	}

	cout << max-1 << endl;

 

그리고 까먹지 말고  max값에 -1을 해줍시다!! (익은 토마토가 1이였어서 -1 해주어야 합니다!)

 

 

bfs는 끝!

 

 

 

 

dfs로 구현 하기위해서는 위방법에서 달라지는것이 몇가지 있을것 같습니다.

1. 일단 큐가 벡터로 변경되어 뒤에서부터 빼오기

2. 날짜를 그냥 채워주는것이 아니라 칸에 들어있는 수와 비교해서 최솟값을 저장해주기....

 

2가지만 바꿔주면 되는데 2번같은경우를 생각하면 연산은 훨씬많아질것 같네요....

 

bfs가 정답인거같습니다.... 

 

 

 

그럼 여기서 끝!

 

 

ALL

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


int M = 0, N = 0;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 }; // 우 좌 상 하

vector<vector<int>>grap(1010, vector<int>(1010, -1));
queue<pair<int,int>>start_p;


int answer = 0;

void find() { // 

	while (start_p.size() != 0) {
		pair<int, int>memo;
		memo = start_p.front();
		start_p.pop();

		int y = memo.first;
		int x = memo.second;

		
		for (int i = 0; i < 4; i++) {
			
			if (grap[y+dy[i]][x + dx[i]] == 0) {
				start_p.push({ y + dy[i] ,x + dx[i] });
				grap[y + dy[i]][x + dx[i]] = grap[y][x]+1;
			}
		}
		
	}

}


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

	cin >> M >> N;
	
	int tomato = 0;

	
	for (int i = 1; i < N+1; i++) { // 1~N까지
		for (int j = 1; j < M+1; j++) {
			cin >> tomato;
			if (tomato == 0) {
				grap[i][j] = tomato;
			}

			if (tomato == 1) {
				grap[i][j] = tomato;
				start_p.push({ i,j });
			}
		}
	}



	find();

	int max = 0;

	for (int i = 1; i < N + 1; i++) { // 며칠만에?
		for (int j = 1; j < M + 1; j++) {
			if (grap[i][j] == 0) {
				cout << -1;
				return 0;
			}

			if (grap[i][j] > max) {
				max = grap[i][j];
			}
		}
		
	}

	cout << max-1 << endl;

	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!