[백준/C++] 7576번_토마토🍅

문제는 다음과 같습니다.

미로찾기에서 조금 더 응용된, bfs응용문제입니다.
bfs 시작전에, 토마토가 익어있는 상태인(1인) 모든 지점을 큐에 넣고 시작해야합니다.
(동시에 익어가므로)

그리고 큐에 넣어야 할 정보는 다음과 같습니다.

✅2차원 배열의 인덱스 정보
✅해당 배열에 있는 토마토가 익는 날짜

pair를 중첩해서 이용하였고, 내부의 pair에는 2차원 배열의 인덱스 값을 넣어주었습니다.

➡️pair<pair<int, int>, int>> p;

해당 부분의 코드는 다음과 같습니다.

for(int i=1; i<=m; i++){
  for(int j=1; j<=n; j++){
    if(a[i][j]==1){
      res=0;
      ch[i][j]=1;
      q.push({{i, j}, res});
    }
  }
}

그리고 bfs가 직접적으로 수행되는 부분은 다음과 같습니다.
토마토가 존재하고, 아직 익지 않았을 때(a[i][j]==0)인 경우에 대해서만,

📌 체크
📌 큐에 push

하면 됩니다.

bfs가 수행되는 부분의 코드는 다음과 같습니다.

// bfs 수행
while(!q.empty()){
  pair<pair<int, int>, int> p = q.front(); q.pop();
  int i = p.first.first; int j = p.first.second; res=p.second;
      

  if(a[i+1][j]==0 && ch[i+1][j]==0 && i+1<=m){
     ch[i+1][j]=1;
     q.push({{i+1, j}, res+1});
  }
  if(a[i-1][j]==0 && ch[i-1][j]==0 && i-1>=1){
     ch[i-1][j]=1;
     q.push({{i-1, j}, res+1});
  }
  if(a[i][j+1]==0 && ch[i][j+1]==0 && j+1<=n){
     ch[i][j+1]=1;
     q.push({{i, j+1}, res+1});
  }
  if(a[i][j-1]==0 && ch[i][j-1]==0 && j-1>=1){
     ch[i][j-1]=1;
     q.push({{i, j-1}, res+1});
  }
} // bfs 끝

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a[1002][1002]={0, };
    int ch[1002][1002]={0, };
    queue<pair<pair<int, int>, int>> q;
    int n, m, res;

    cin>>n>>m;
    for(int i=1; i<=m; i++){
      for(int j=1; j<=n; j++){
        int tmp; cin>>tmp;
        a[i][j]=tmp;
      }
    } // 배열 입력 완료

    for(int i=1; i<=m; i++){
      for(int j=1; j<=n; j++){
        if(a[i][j]==1){
          res=0;
          ch[i][j]=1;
          q.push({{i, j}, res});
        }
      }
    }
    
    // bfs 수행
    while(!q.empty()){
      pair<pair<int, int>, int> p = q.front(); q.pop();
      int i = p.first.first; int j = p.first.second; res=p.second;
      

      if(a[i+1][j]==0 && ch[i+1][j]==0 && i+1<=m){
        ch[i+1][j]=1;
        q.push({{i+1, j}, res+1});
      }
      if(a[i-1][j]==0 && ch[i-1][j]==0 && i-1>=1){
        ch[i-1][j]=1;
        q.push({{i-1, j}, res+1});
      }
      if(a[i][j+1]==0 && ch[i][j+1]==0 && j+1<=n){
        ch[i][j+1]=1;
        q.push({{i, j+1}, res+1});
      }
      if(a[i][j-1]==0 && ch[i][j-1]==0 && j-1>=1){
        ch[i][j-1]=1;
        q.push({{i, j-1}, res+1});
      }
    } // bfs 끝
    
    for(int i=1; i<=m; i++){
      for(int j=1; j<=n; j++){
        if(a[i][j]==0 && ch[i][j]==0){
          cout<<"-1\n";
          return 0;
        }
      }
    }

    cout<<res<<endl;
    return 0;
}

그리고 마지막 부분에서,
❗️토마토가 모두 익지 못하는 예외가 발생할 수 있으므로,
이에대한 예외처리를 해야 합니다.

전체 배열을 돌면서, 해당 배열에 토마토가 존재하지만 ch가 되어있지 않으면
해당 토마토는 익지못한 것이므로, 여기부분에서 예외처리를 수행하면 됩니다.

---

2/19 토요일 복습)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int a[1002][1002]={0, }; int ch[1002][1002]={0, };
  queue<pair<pair<int, int>, int>> q; int n, m, day;
  cin>>m>>n;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      cin>>a[i][j];
      if(a[i][j]==1) { ch[i][j]=1; q.push({{i, j}, 0}); }
    }
  }

  while(!q.empty()){
    pair<pair<int, int>, int> p = q.front(); q.pop();
    int t1 = p.first.first; int t2 = p.first.second; day = p.second;

    if(t1+1<=n && a[t1+1][t2]==0 && ch[t1+1][t2]==0){
      ch[t1+1][t2]=1; q.push({{t1+1, t2}, day+1});
    }
    if(t2+1<=m && a[t1][t2+1]==0 && ch[t1][t2+1]==0){
      ch[t1][t2+1]=1; q.push({{t1, t2+1}, day+1});
    }
    if(t1-1>=1 && a[t1-1][t2]==0 && ch[t1-1][t2]==0){
      ch[t1-1][t2]=1; q.push({{t1-1, t2}, day+1});
    }
    if(t2-1>=1 && a[t1][t2-1]==0 && ch[t1][t2-1]==0){
      ch[t1][t2-1]=1; q.push({{t1, t2-1}, day+1});
    }
  }
  

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(ch[i][j]==0 && a[i][j]==0) { cout<<"-1"; return 0; }
    }
  }
  cout<<day;
  return 0;
}