백준 7569 - 토마토

https://www.acmicpc.net/problem/7569

7569번: 토마토

문제

---

토마토 상자에는 익은 토마토, 안익은 토마토, 비어 있는 경우 3가지의 경우가 존재한다.

정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

이러한 N개의 줄이 H번 반복하여 주어진다.

토마토 상자 

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

 

 

 

접근 방법 및 풀이

---

BFS로 풀이가 가능하다 3차원의 공간으로 토마토가 위치해 있으므로 3차원 배열을 사용했다.

여기서 각각의 최대의 개수는 100이므로 int로 해도 무방하다.

 

1. 토마토 상자를 표현할 수 있는 배열을 선언한다.

2. 각각의 상자에서 익은 토마토의 위치와 들어있지 않은 토마토의 위치를 파악하여 데이터를 저장한다.

3. 익은 토마토의 위치를 Queue에 저장하여 주위 토마토를 익은 토마토로 변환한다.

4. 3번의 과정에서 BFS 를 적용하고 익은 토마토를 다시 Queue에 저장하고, Queue가 비면 그 동안 소요된 시간을 출련한다.

 

다음 문제는 배열에서 x,y,z와 실제 좌표에서의 x,y,z의 구별을 확실하게 할줄 안다면 손쉽게 접근할 수 있습니다~.

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int N,M,H;
int cnt=0;
int box[101][101][101];
int isvisit[101][101][101];

int dx[] = { -1,1,0,0,0,0 };	//상,하,좌,우,위,아래 배열
int dy[] = { 0,0,0,0,-1,1};
int dh[] = { 0,0,-1,1,0,0 };

queue<pair<pair<int, int>, int> > q;	//토마토의 위치를 저장할 queue

void spread(){	//익은 토마토가 다른 토마토로 전염시키는 함수
    while(!q.empty()){
        int ofsize= q.size();
        cnt++;
        while(ofsize--){	//처음의 익은 토마토의 위치의 개수 만큼 반복 
            pair<pair<int, int>, int> now = q.front(); 
            // 이 부분은 원래 int curx= q.front().first.second 와 같은 형식으로 작성해도 되지만,
            // 다음의 형식이 유용하여 판단하여 제시하였습니다.
            q.pop();
            for(int i=0;i<6;i++){	//상,하,좌,우,위,아래 search
                int nx = now.first.second  + dx[i];
                int ny = now.first.first + dy[i];
                int nh = now.second + dh[i];
 
                if (nx < 0 || nx >= M || ny < 0 || ny >= N|| nh < 0 || nh >= H)continue;
                if (!isvisit[ny][nx][nh] && box[ny][nx][nh] == 0){
                    isvisit[ny][nx][nh] = true;
                    q.push(make_pair(make_pair(ny, nx), nh));
                }
                
            }
            
        }
        
    }
}
int main(){
    memset(box,0,sizeof(box));
    memset(isvisit,0,sizeof(isvisit));    
    scanf("%d %d %d",&M,&N,&H);

    for(int i=0; i<H;i++){
        for(int l=0;l<N;l++){
            for(int m=0;m<M;m++){
                scanf("%d",&box[l][m][i]);
                if(box[l][m][i]==1){    // 익은 토마토 칸
                    isvisit[l][m][i]=1;
                    // printf("%d %d %d\n",l,m,i);
                    q.push(make_pair(make_pair(l,m),i));
                }
            
                else if (box[l][m][i]==-1){  // 들어있지 않은 토마토 칸
                    isvisit[l][m][i]=1;
                }
            }
        }
    }

    spread();
    // 안 익은 토마토가 존재하면 -1을 리턴
    for(int a=0;a<H;a++){
        for(int b=0;b<N;b++){
            for(int c=0;c<M;c++){
                if(!isvisit[b][c][a]){
                    printf("-1\n");
                    return 0;
                }
            }
        }
    }
    printf("%d\n",cnt-1);
    return 0;
}

 

 

Funny Algorithms~ :0