[BOJ/7569] 토마토, c++

www.acmicpc.net/problem/7569

7569번: 토마토

한줄 후기 : 방울 토마토 먹고 싶다.

acmicpc.net/problem/7576

7576번: 토마토

이 문제랑 똑같다. 

대신 7569 번은 3차원 공간에서 토마토가 존재한다고 생각하면 됨.

그래서 그냥 3차원 배열을 만들어줬다.

tomato[H][N][M] 이런식으로 저장해줌.

주의해야할게 당연히 M 이 행이고 N이 열로 들어올 줄 알았는데 반대였다.

 

//AC
//BOJ 7569 토마토
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define SIZE 101
using namespace std;
int day[SIZE][SIZE][SIZE];
int tomato[SIZE][SIZE][SIZE];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int dh[2] = { 1, -1 };
struct Index{
	int h, m, n;
};
int main(){
	int M, N, H;
	queue<Index> q;
	cin >> N >> M >> H;
	int tmp = 0;
	while(tmp < H){
		for(int i=0; i<M; i++){
			for(int j=0; j<N; j++){
				day[tmp][i][j] = -1;
				scanf("%d", &tomato[tmp][i][j]);
				if(tomato[tmp][i][j] == 1){
					day[tmp][i][j] = 0;
					q.push({tmp, i, j});
				}
			}
		}
		tmp += 1;
	}
	while(!q.empty()){
		int h1 = q.front().h;
		int m1 = q.front().m;
		int n1 = q.front().n;
		q.pop();
		for(int i=0; i<4; i++){
			int nx = m1+dx[i];
			int ny = n1+dy[i];
			if(nx < 0 || ny < 0 || nx >= M || ny >= N)	continue;
			if(tomato[h1][nx][ny] == 0 && day[h1][nx][ny] == -1){
				day[h1][nx][ny] = day[h1][m1][n1] + 1;
				q.push({h1, nx, ny});
			}
		}
		for(int i=0; i<2; i++){
			int nh = h1+dh[i];
			if(nh < 0 || nh >= H)	continue;
			if(!tomato[nh][m1][n1] && day[nh][m1][n1] == -1){
				day[nh][m1][n1] = day[h1][m1][n1] + 1;
				q.push({nh, m1, n1});
			}
		}
	}
	int ans = 0;
	for(int i=0; i<H; i++){
		for(int j=0; j<M; j++){
			for(int k=0; k<N; k++){
				ans = max(ans, day[i][j][k]);
				if(day[i][j][k] == -1 && !tomato[i][j][k]){
					printf("-1");
					return 0;
				}
			}
		}		
	}
	printf("%d" , ans);
	return 0;
}

 

복잡해 보이지만 사실 간단한 bfs 문제라 생각하면 된다.

queue를 이용할건데, 여기서 day 배열은 해당 위치 토마토가 익을 때 까지 걸린 day를 의미한다.

구조체를 이용해 위치 index를 저장할 것이다. 

같은 높이에 있는 토마토는 상하 좌우만 보면 되니 dx, dy 배열을 세팅해준다.

dh 배열을 새로 만들어줬는데 이는 다른 높이, 즉 위, 아래 인덱스를 계산해줄 배열이다.

 

미리 익어있는 토마토는 입력 받을 때, day를 0으로 세팅하고 큐에 넣어 두었다.

큐가 비어있지 않다면 계속해서 상,하,좌,우,위,아래를 돌면서 day = -1이고 (아직 안익은=방문 X) and tomato = 0 (토마토가 존재하는 칸) 이라면 해당 위치 day = 현재 위치 day + 1 해주면 된다.

모든 탐색이 끝나면, 전체적으로 안익은 토마토가 존재하는지 확인하면서 (만약 존재한다면 바로 -1출력!)

max answer를 갱신해준다. 

 

7576 문제랑 거의 비슷한데 다른 높이 토마토 상자를 한번 더 계산해줘야하는 문제였다.

7576을 먼저 풀고 풀면 쉬울 듯