[7569] 토마토(C++)

1. 문제

www.acmicpc.net/problem/7569

7569번: 토마토

2. 접근 방법

1) 3차원 벡터를 사용한다는 것 외에는 일반적인 bfs 문제

 

2) 초기 box[h][x][y]에는 토마토 정보를 입력한다.( 1: 익은 토마토, 0 :안익은 토마토, -1: 토마토 없음)

 

3) 초기에 안익은 토마토의 개수 cnt를 저장한다.

 

4) bfs를 돌면서 box에는 해당 토마토가 익을 때까지 걸린 날짜 +1 을 저장하면서, cnt == 0 일때까지 bfs를 돈다. 만약 while문을 빠져나왔다면 모든 토마토가 익지 못했다는 뜻이므로 -1을 출력한다.

if(box[nh][nx][ny] == 0) {
	box[nh][nx][ny] = box[ch][cx][cy]+1;
	if(--cnt == 0) {
		cout << box[nh][nx][ny]-1<<endl;
		return 0;
	}
	else q.push(make_tuple(nh,nx,ny));
}

 

3. 실수했던 부분 & 처음 알았던 부분

1) bad_alloc()에러가 계속 났음

  - int N,M,H; 값을 입력받지 않은 채로 vector를 선언했었다.

  => int N,M,H;와 같은 사이즈 변수는 선언 후 바로 입력 받자. (괜히 선언부 구현부 나누려고 하다가 다음과 같은 실수를 했었다..)

 

 

2) bfs를 사용할 때 반드시 사용해야 하는 것

 * queue

 * 방향을 나타내는 배열 dir[]; 

 (참고 : visited는 굳이 따로 선언하지 않고 배열 값 자체로 판단 가능한 경우도 있다.)

 

 

3) 걸린 날짜를 저장하는 법 2가지

   * 큐에 변수로 저장하기 : 가장 자주 쓰는 법. 해당 방법을 쓸 때는 tuple을 헤더로 추가하는 것 잊지 말기. 실제 코테 때는 위 방식을 쓰도록 하자(내가 익숙하므로).  

 

  * 배열 값으로 저장하기 : 해당 문제에서 사용한 방법. box에 걸린 날짜를 저장하는 방식 사용 

   --- box[nh][nx][ny] = box[ch][cx][cy] + 1 ; 이렇게 구하면 모든 토마토가 익었을 때, box값으로 출력이 가능하다.

   --- 단, 이 때 2일부터 시작되므로 마지막 출력값엔 -1을 빼야 하는 것 잊지 말기!!!

   --- bfs를 사용해서 "전체 소요 날짜"만 구해야 하는 간단한 문제의 경우에는 사용할 수 있을 것 같다. 

 

 

4) 3차원 벡터 선언 방법

vector< vector <vector<int> > >box(H,vector<vector<int>>(N,vector<int>(M)));  // >>> 개수 유의하기

 

 

5) 모든 토마토가 익었는지 확인하는 법 

 1. 마지막에 모든 배열을 돌면서 box[h][x][y] == 0 인 값이 있는지 확인하기

 2. 안익은 토마토 개수 cnt 저장 -> bfs를 돌다 안익은 토마토를 익게 하면 --cnt 처리 -> cnt == 0 이면 바로 종료 

  (단, 이 방식은 bfs 시작전 cnt ==0 일때의 예외처리를 해야 함!!) // 2번 방식이 익숙해지도록 연습하기

 

 

4. 코드

#include<iostream>
#include<queue>
#include<tuple>
#include<vector>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	//1.필요한 구조체 선언 
	tuple<int,int,int> dir[6] = {{1,0,0},{-1,0,0},{0,-1,0},{0,1,0},{0,0,1},{0,0,-1} }; // 6방향 
	int M,N,H; // M: 가로칸,N:세로칸,H:높이
	cin >> M >> N >> H; 
	vector< vector <vector<int> > >box(H,vector<vector<int>>(N,vector<int>(M)));
	queue<tuple<int,int,int > > q; //높이,세로, 가로
	int cnt = 0; //안익은 토마토 개수

	//2.box에 토마토 정보 입력
	for(int i=0;i<H;i++) {
		for(int j=0;j<N;j++) {
			for(int k=0;k<M;k++) {
			cin >> box[i][j][k];
			if(box[i][j][k] == 1 ) q.push(make_tuple(i,j,k));
			if(box[i][j][k] == 0 ) cnt++;
			}	
		 }
	}
	if(cnt == 0 )  { // 예외 : 처음부터 모든 토마토가 익었을 때 
	 	cout <<0 <<endl;
		return 0;
	}

	//3. bfs
	while(!q.empty()) {
		int ch = get<0>(q.front());
		int cx = get<1>(q.front());
		int cy = get<2>(q.front());
		q.pop();
		
		for(int i=0;i<6;i++) {
			int nh = ch + get<0>(dir[i]);
			int nx = cx + get<1>(dir[i]);
			int ny = cy + get<2>(dir[i]);
		
			if(nh < 0 || nh >= H || nx < 0 || nx >= N || ny <0 || ny >=M)	continue;
			if(box[nh][nx][ny] == 0) {
				 box[nh][nx][ny] = box[ch][cx][cy]+1;
				 if(--cnt == 0) {
					cout << box[nh][nx][ny]-1<<endl;
					return 0;
				 }
				 else 
				  q.push(make_tuple(nh,nx,ny));
			}
		}
	}
	//모든 토마토가 익지 못했음
	cout<<-1<<endl;
	return 0;
}