[BOJ - 7576] 토마토

💡문제 한마디

2차원 배열을 BFS를 통해 탐색하는 문제로, 갈 수 있는 방향은 최소 2방향에서 최대 4방향으로 0이면 방문하고 아니면 방문하지 않는 문제

👉문제 링크

토마토

🖥️코드

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

using namespace std;

int arr[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int zerocount =0;

queue<pair<int,int>> q;

bool isTrue(int r,int c,int row, int col);
int BFS(int row, int col, vector<vector<int>> v);

int main(void){
  int row,col;
  int tem;
  int minuscount=0;

  cin >> col >> row;
  vector<vector<int>> v(row,vector<int>(col));
  for(int i=0;i<row;i++){
    for(int j=0;j<col;j++){
      scanf("%d",&tem);
      v[i][j] = tem;
      if(tem==1){
        q.push(make_pair(i,j));
        continue;
      }
      if(tem==-1){
        minuscount++;
        continue;
      }
      zerocount++;
      
    }
  }
  if(!zerocount){
    cout << 0;
    return 0;
  }
  if(!q.size()){
    cout << -1;
    return 0;
  }

  int count = BFS(row,col,v);

  if(zerocount){
    cout << -1;
    return 0;
  }
  else{
    cout << count-1;
    return 0;
  }
  
}

bool isTrue(int r,int c,int row, int col){
  if(r<0 || r>=row){
    return false;
  }
  if(c<0 || c>=col){
    return false;
  }
  return true;
}

int BFS(int row, int col, vector<vector<int>> v){
  int count =0;
  pair<int,int> tem;
  int size =q.size();
  int tr,tc;
  while(size){
    count ++;
    for(int i=0;i<size;i++){
      tem = q.front();
      q.pop();
      for(int j=0;j<4;j++){
        tr = tem.first+arr[j][0];
        tc = tem.second+arr[j][1];
        if(isTrue(tr,tc,row,col) && v[tr][tc]==0){
          q.push(make_pair(tr,tc));
          v[tr][tc] = 1;
          zerocount --;
        }
      }
    }
    size=q.size();
  }
  return count;
}

📎풀이

🗝️KeyPoint

1. -1 이거나 1 인 경우에는 방문하지 않아도 됨.
2. 전날 방문한 곳 주위 0 인 경우에는 다음 날 무조건 방문해야 함

int arr[4][2] = {{1,0},{-1,0},{0,-1},{0,1}}; // 4방위 지정
int zerocount =0; 

queue<pair<int,int>> q;

bool isTrue(int r,int c,int row, int col); // 갈 수 있는 곳이 맞는지 아닌지 판별하는 함수
int BFS(int row, int col, vector<vector<int>> v); // 탐색 함수

int main(void){
  int row,col;
  int tem;
  int minuscount=0;

  cin >> col >> row;
  vector<vector<int>> v(row,vector<int>(col));
  for(int i=0;i<row;i++){
    for(int j=0;j<col;j++){
      scanf("%d",&tem);
      v[i][j] = tem;
      if(tem==1){
        q.push(make_pair(i,j));
        continue;
      }
      if(tem==-1){
        minuscount++;
        continue;
      }
      zerocount++;
      
    }
  }
  if(!zerocount){ // 0이 없다는 것은 이미 해결했다는 것이니 BFS들어가기 전에 0 출력하고 리턴
    cout << 0;
    return 0;
  }
  if(!q.size()){ // q.size가 없는데 0이 있다는 것이니까 -1 출력
    cout << -1;
    return 0;
  }

  int count = BFS(row,col,v); // 탐색해서 count를 반환 받음

  if(zerocount){ // 모든 곳을 돌아다녀도 0이 존재한다면 -1을 출력해야 함.
    cout << -1;
    return 0;
  }
  else{
    cout << count-1; // BFS함수를 보면 모든 곳이 1이 되어도 q가 있기 때문에 한번 더 돌게 되어 있음 그러므로 count-1이 답임.
    return 0;
  }
  
}

bool isTrue(int r,int c,int row, int col){
  if(r<0 || r>=row){ // 0<=r<row 이여야지 true
    return false;
  }
  if(c<0 || c>=col){ 0<=c<col 이여야지 true
    return false;
  }
  return true;
}

• 주석으로 설명 대체

int BFS(int row, int col, vector<vector<int>> v){
  int count =0;
  pair<int,int> tem;
  int size =q.size();
  int tr,tc;
  while(size){ // queue가 비어있을 경우에 반복문 종료
    count ++;
    for(int i=0;i<size;i++){ // 설명 2 참고
      tem = q.front();
      q.pop();
      for(int j=0;j<4;j++){
        tr = tem.first+arr[j][0];
        tc = tem.second+arr[j][1];
        if(isTrue(tr,tc,row,col) && v[tr][tc]==0){ // 설명 1 참고
          q.push(make_pair(tr,tc)); //설명 3 참고
          v[tr][tc] = 1;
          zerocount --;
        }
      }
    }
    size=q.size();
  }
  return count;
}

==설명==

1. 기존 BFS 알고리즘에서 방문 여부를 확인하는 것은 '0'인지 아닌지 판별로 대체하면 됨
2. 기존 queue 크기를 받아온 후 그만큼 반복하는 과정이 1일 지난 것으로 보면 됨.
3. 기존 0 이었던 주위에 0은 다음 날 1로 만들어주어야 하므로 queue에 다시 넣어줌.

📖배운 점

• pair라는 STL을 사용하면 2차원 배열의 index를 구현할 때 구분하기 좋음