[C++] 백준 7576 : 토마토

#include <iostream>
#include <queue> // bfs - 인접된 것 cnt 해야해서
#include <utility> // x, y 좌표 저장
using namespace std;

int M, N; //가로, 세로
int map[1001][1001]; // 상자 1 : 익은 토마토 0 : 안 익은 토마토 -1 : 토마토가 없음
bool visited[1001][1001] = {false}; // 방문 여부
queue<pair<int, int> > q; // x, y

// 상하좌우 체크
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool allTomato = false; // 처음부터 다 익은 경우
int cnt = 0; // 처음부터 모든 토마토 익어있으면 0, 모두 못 익으면 -1

void BFS(){
  while(!q.empty()){ // 인접 없을 때 까지 반복
    int x = q.front().first;
    int y = q.front().second; // 노드에서 좌표 꺼내기
    q.pop();

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(nx < 1 || ny < 1 || nx > N || ny > M){ // 범위 체크 잘 하기
        continue;
      }

      if(map[nx][ny] == 0 && !visited[nx][ny]){ // 안익고 방문 안된 토마토
        map[nx][ny] = map[x][y] + 1; // 토마토 익는 순서
        q.push(make_pair(nx, ny)); // 큐에 넣기
        visited[nx][ny] = true; // 방문 체크
      }
    }
  }

}

int main(int argc, char** argv){
  scanf("%d %d", &M, &N);

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= M; j++){
      scanf("%d", &map[i][j]);
      if(map[i][j] == 0){
        allTomato = true; // 안 익은 토마토 있는 경우
      }
    }
  }

  if(!allTomato){ // 처음부터 모든 토마토 익은 경우
    printf("0");
    return 0;
  }
  
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= M; j++){
      if(map[i][j] == 1 && !visited[i][j]){
        q.push(make_pair(i,j)); // 토마토 큐에 넣기
        visited[i][j] = true; // 방문 체크
      }
    }
  }

  BFS();
  
  // for(int i = 1; i <= N; i++){
  //   for(int j = 1; j <= M; j++){
  //     printf("%d ", map[i][j]);
  //   }
  //   printf("\n");
  // }


  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= M; j++){
      if(map[i][j] == 0){
        printf("-1"); // 안 익은 토마토 있을 경우
        return 0;
      }
      if(cnt < map[i][j]){ // 최대값 찾기
        cnt = map[i][j];
      }
    }
  }

  printf("%d", cnt-1); // 익은 토마토는 1부터 시작하기 때문에

  return 0;
}

처음에는 그래프 탐색이라 DFS로 풀었는데 인접된 것을 차례로 카운트 해나가야 했기 때문에 BFS로 다시 푼 문제다

• cnt를 할 때 점진적으로 증가한다. 따라서 변수를 따로 두는 것이 아니라 맵에서 cnt를 증가시켜 맵에서 cnt를 세도록 하였다.

헷갈리는 BFS와 DFS 정리

BFS

• BFS는 큐를 사용한다.

• 탐색할 항목은 큐에 넣는다. while을 사용하여 큐가 빌 때 까지 탐색한다. 탐색하였을 때 인접항목(for문)을 확인하여 조건에 맞는 경우 큐에 넣는다. 방문하면 큐에서 pop한다.

DFS

• DFS는 재귀 함수를 사용한다.

• 탐색할 항목은 재귀 함수의 parameter에 넣는다. 재귀함수는 탐색 여부를 표시하고 인접 노드를 탐색한다. 조건에 맞는 경우 재귀 함수의 parameter에 해당 값을 넣고 재귀함수 시킨다.