Boj 7576 & 7569 c++ 토마토

그래프 탐색에 있어 BFS확산형 탐색의 기본이 되는 문제이다. 현재까지 푼 문제중에서 dist벡터(레벨벡터)를 처음으로 사용하는 문제였다. 

 

2차원 토마토

 

3차원 토마토

문제는 간단했다. 위의 그림과 같은 토마토 상자가 있을 때 입력으로 각 상자에 저장되어있는 토마토의 상태가 주어진다. 토마토가 익지 않았으면 0, 토마토가 익었으면 1, 토마토가 들어있지 않은 공간에는 -1이 입력된다.

 

이때, 하루가 지나면 익은 토마토와 인접해 있는 토마토들은 모두 익어버린다. 이때, 인접한다는 것의 의미는 2차원일때 상하좌우(4방향) 3차원일때 위 아래 오른쪽 왼쪽 앞 뒤(6방향)을 의미한다.

 

상자에 있는 토마토가 모두 익을 때까지 걸리는 최소 일수를 구하는 것이 문제이다. 토마토가 모두 익는 것이 불가능한 경우에는 -1을 출력하고, 이미 모두 익어있는 상태에서는 0을 출력한다.

 

 

코드를 짜기 이전에 드는 가장 큰 의문은 다음과 같았다.

 

'익은 토마토는 한두개가 아닌데 어떻게 동시에 확산하는 것을 구현하고,  최소 날짜 수를 구하는 cnt를 꼬이지 않게 배치하지???'

 

하지만 이 의문은 바로 이전에 풀었던 '미로탐색'에서 문제를 풀었던 방식을 떠올리고 나니 해소되었다. 또한 동시다발적으로 확산하는 것 또한 내가 각각의 레벨별 확산 별로 시간을 하나씩 더해주면 된다는 BFS의 특성으로 해결이 되는 것이였다. 하지만 가장 크게 우려되었던 점은 '큐에 집어넣어도 실행되는 시간차가 존재하는데 그러면 최소일수를 구하는 dist값이 덮어씌워질 수도 있지 않나?'였다.

 

하지만 이 문제도 BFS의 레벨별 탐색으로 해결될 수 있었다. BFS는 1단계, 2단계씩 점점더 넓은 공간을 탐색해나가는 알고리즘이다. 때문에 가장 처음 도달한 경로가 곧 최단경로이다. 또한 큐에 입력되고 실행되는 시간차가 발생한다고 하더라도 순차적으로 큐에 push되는 알고리즘의 구조상 레별별로 각각 독립적으로 이루어지기 때문에 값이 왜곡될 위험이 전혀 존재하지 않는다. 

이로써 작성한 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<vector<int>> v(1001, vector<int>(1001));
vector<vector<int>> dist(1001, vector<int>(1001, -1));
queue<pair<int, int>> q;
int N, M;

void tomato(){



   int dx[4]={-1, 1, 0, 0};
   int dy[4]={0, 0, 1, -1};



   for(int i=1; i<=M; i++){
       for(int j=1; j<=N; j++){
          if(v[i][j]==1){
          q.push({i, j});
          dist[i][j]=0;}
       }

   }


   while(!q.empty()){

        int U=q.front().first;//U, V값 초기화
        int V=q.front().second;

       for(int i=0; i<4; i++){


            int nx=dx[i]+U;//4방향 탐색
            int ny=dy[i]+V;

            if(nx<1 || ny<1 || nx>M || ny>N)//인덱스 이탈 방지
            continue;


            if(v[nx][ny]==0 && dist[nx][ny]==-1){//토마토 익지 않았으며, 미방문인 경우
                q.push({nx, ny});//탐색 예약
                dist[nx][ny]=dist[U][V]+1;//날짜 수 누적

               }
            }
          q.pop();//4방향 탐색이 끝난 이후 pop
    }

}


int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    cin>>N>>M;

    for(int i=1; i<=M; i++){

        for(int j=1; j<=N; j++){
            cin>>v[i][j];
        }
    }

    tomato();
    int Max=-999;
    for(int i=1; i<=M; i++){
        for(int j=1; j<=N; j++){
            if(v[i][j]==0 && dist[i][j]==-1){
                cout<<"-1";
                return 0;
            }
            Max=max(dist[i][j], Max);
        }
    }
    cout<<Max;




}

*2차원

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<vector<vector<int>>> v(101, vector<vector<int>>(101, vector<int>(101)));
vector<vector<vector<int>>> dist(101, vector<vector<int>>(101, vector<int>(101, -1)));
queue<pair<pair<int, int>, int>> q;
int N, M, H;

void tomato(){



   int dx[6]={-1, 1, 0, 0, 0, 0};
   int dy[6]={0, 0, 1, -1, 0, 0};//위, 아래, 왼쪽, 오른쪽, 앞, 뒤
   int dz[6]={0, 0, 0, 0, -1, 1};



   for(int i=1; i<=H; i++){
       for(int j=1; j<=N; j++){
           for(int k=1; k<=M; k++){
              if(v[i][j][k]==1){
                  q.push({{i, j}, k});
                  dist[i][j][k]=0;}
           }
       }

   }


   while(!q.empty()){

        int U=q.front().first.first;//U, V, W값 초기화
        int V=q.front().first.second;
        int W=q.front().second;

       for(int i=0; i<6; i++){


            int nx=dx[i]+U;//6방향 탐색
            int ny=dy[i]+V;
            int nz=dz[i]+W;

            if(nx<1 || ny<1 || nz<1 || nx>H || ny>N || nz>M)//인덱스 이탈 방지
            continue;


            if(v[nx][ny][nz]==0 && dist[nx][ny][nz]==-1){//토마토 익지 않았으며, 미방문인 경우
                q.push({{nx, ny}, nz});//탐색 예약
                dist[nx][ny][nz]=dist[U][V][W]+1;//날짜 수 누적

               }
            }
          q.pop();//6방향 탐색이 끝난 이후 pop
    }

}


int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    cin>>M>>N>>H;//M은 열 N은 행 H는 높이

    for(int i=1; i<=H; i++){

        for(int j=1; j<=N; j++){

            for(int k=1; k<=M; k++){
                 cin>>v[i][j][k];
            }
        }
    }

    tomato();
    int Max=-999;
    for(int i=1; i<=H; i++){
        for(int j=1; j<=N; j++){
            for(int k=1; k<=M; k++){
            if(v[i][j][k]==0 && dist[i][j][k]==-1){
                cout<<"-1";
                return 0;
            }
            Max=max(dist[i][j][k], Max);
            }
        }
    }
    cout<<Max;




}

*3차원

 

2차원 코드를 3차원으로 바꿀시에 가장 주의해야 하는 점은 중첩 for문의 순서이다  어떤 입력값이 행, 열, 높이 인지에 따라서 for문의 인자값이 달라질 수 있다. 이는 이후에 디버깅할 때에도 알아보기 힘들기 때문에 반드시 코드를 짜는 중에 입력순서와 for문의 인자값이 일치하는지 확인하도록 하자.

 

 

 

또한 이후에 함수로 구해낸 최소일수와 토마토가 모두 익었는지에 대한 사실 여부를 확인하는 방법또한 익혀두어야 한다.

최소일수는 곧 dist에 저장된 가장 큰 값이기 때문에 3중 for문을 사용하여 최댓값을 찾는다. 

 

하지만 토마토가 모두 익지 못한 상황에 대한 예외처리가 헷갈릴 수 있다. 그러나 이는 입력받은 익지 않은 토마토들 중 방문처리가 되지 않은 것이 하나라도 존재하면 -1을 출력하도록 해주면 해결된다.