[백준] 2636번 치즈 (C++) - BFS

문제

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

2636번: 치즈

코드

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

using namespace std;

int r,c;
int hour = 0;
int cheese[100][100];
bool isVisited[100][100];

// 동, 남, 서, 북 
int dy[4] = {0,1,0,-1};
int dx[4] = {1,0,-1,0};

void initVisited(){
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      isVisited[i][j]=false;
    }
  }
}

bool inRange(int y, int x){
  return (0<=y&&y<r&&0<=x&&x<c);
}

int bfs(){
  isVisited[0][0] = true;
  int cnt=0;
  queue<pair<int, int>> q;
  q.push({0,0});
  hour++;
  while(!q.empty()){
    int y = q.front().first;
    int x = q.front().second;
    q.pop();
    for(int i=0; i<4; i++){
      int ny=y+dy[i];
      int nx=x+dx[i];
      if(inRange(ny, nx) && !isVisited[ny][nx]){
        if(cheese[ny][nx]==0) q.push({ny,nx});
        else{
          cheese[ny][nx]=0;
          cnt++;
        }
        isVisited[ny][nx]=true;
      }
    }
  }
  return cnt;
}


int main(){
  cin >> r >> c;
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      cin >> cheese[i][j];
    }
  }
  int preCheeseCnt;
  while(true){
    initVisited();
    int cheeseCnt = bfs();
    if(cheeseCnt==0){
      cout << hour-1 << '\n' << preCheeseCnt;
      break;
    }else preCheeseCnt=cheeseCnt;
  }
  return 0;
}

정리

이 문제에서 중요한 점은 공기와 접촉한 치즈 개수만 세어도 된다는 것이다. 왜나하면 치즈가 다 녹기 전 한 시간 전에 치즈들은 모두 공기와 접촉하기 때문이다. 처음에는 모든 치즈의 개수(공기와 접촉하지 않는 치즈들까지)를 다 세려고 했더니 문제가 잘 풀리지 않았다. 그래서 다른 사람들의 풀이를 보았고 치즈 바깥을 bfs로 돌면서 공기와 치즈가 닿는 부분만을 count해서 문제를 해결했다.

참조

https://ongveloper.tistory.com/159