[BFS & DFS] tomato

[BFS & DFS] tomato

[BFS: Breath First Search] - 재귀함수(스택)

깊이까지 들어가서 탐색하고 다시 돌아오는 알고리즘;

백트래킹 알고리즘에 활용되는 개념이다.

주로 스택을 이용한다. (재귀함수의 콜스택)

최대 탐색 횟수를 구하는 경우, 기존 담긴 값과 이번에 담을 값을 비교해서 탐색을 계속할지 확인한다.

[DFS: Depth First Search] - 큐

순서대로 닿는 곳을 탐색하는 알고리즘;

큐에 순서대로 저장해서 하나씩 빼면서 확인한다.

계속 큐에 집어넣고, 하나씩 꺼내면서 큐가 빌때까지 계속 반복한다.

큐에 담기는 순서대로 값이 증가하기 때문에 기존에 담긴 값을 확인할 필요가 없다. 값이 없는 경우에만 새롭게 담는다.

// tomato BFS(Breath First Search)
// queue & utility > pair
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

#define SIZE 1001

int w, h;
int tomato[SIZE][SIZE];

typedef pair<int, int> POS;
queue<POS> q;

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

int main() {
   cin >> w >> h;
   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         cin >> tomato[i][j];
      }
   }

   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         if(tomato[i][j] == 1) {
            POS pos = make_pair(j, i);
            q.push(pos);
         }
      }
   }

   while(!q.empty()) {
      POS next = q.front();
      q.pop();

      int x = next.first;
      int y = next.second;

      int value = tomato[y][x];
      for(int k=0; k<4; k++) {
         int nx = x+dx[k];
         int ny = y+dy[k];
         if(nx < 0 || ny < 0 || ny >= h || nx >= w) {
            continue;
         }

         if(tomato[ny][nx] == 0) {
            tomato[ny][nx] = value+1;

            POS p = make_pair(nx, ny);
            q.push(p);
         }
      }
   }

   bool isComplete = true;
   int max = 0;
   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         int value = tomato[i][j];
         if(value == 0) {
            isComplete = false;
            break;
         }

         max = (max < value || max == 0) ? value : max;
      }
      if(!isComplete) break;
   }

   max--; // first is count 2; nothing 0-1 = -1;
   cout << (isComplete ? max : -1) << endl;

   return 0;
}

// tomato DFS(Depth First Search)
#include <iostream>
using namespace std;

#define SIZE 1000

int w, h;
int tomato[SIZE][SIZE];

void spread(int x, int y, int value) {
   if(x < 0 || y < 0 || y > h || x > w) {
      return;
   }

   if(tomato[y][x] == -1 ||
      tomato[y][x] && tomato[y][x] < value) {
      return;
   }

   tomato[y][x] = value++;

   spread(x-1, y, value); // left
   spread(x+1, y, value); // right
   spread(x, y-1, value); // top
   spread(x, y+1, value); // bottom
}

int main() {
   cin >> w >> h;
   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         cin >> tomato[i][j];
      }
   }

   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         if(tomato[i][j] == 1) spread(j, i, tomato[i][j]);
      }
   }

   bool isComplete = true;
   int max = 0;
   for(int i=0; i<h; i++) {
      for(int j=0; j<w; j++) {
         int value = tomato[i][j];

         if(tomato[i][j] == 0) {
            isComplete = false;
            break;
         }

         if(max == 0) {
            max = value;
         } else {
            max = max < value ? value : max;
         }
      }
      if(!isComplete) {
         break;
      }
   }

   max--; // first is count 2;
   cout << (isComplete ? max : -1) << endl;

   return 0;
}