DFS BFS

BFS - 너비우선 탐색

 

큐에 그래프의 정점들을 넣고 앞에서 부터 pop 시키면서 pop된 정점과 연결된 정점을 큐에 push 하여 모든 정점을 탐색하는 알고리즘.

최단경로를 찾을 수 있다.

 

DFS - 깊이우선탐색

 

한 정점에서 시작해서 재귀적으로 인접노드들을 파고들어 탐색하는 알고리즘

 

 

BFS 문제 - (www.acmicpc.net/problem/2178)

#include <iostream>
#include <queue>
using namespace std;

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

  int n, m;
  cin >> n >> m;

  int arr[101][101] = {0};
  int d[101][101] = {0};
  bool c[101][101] = {false};
  d[0][0] = 1;
  c[0][0] = true;


  for(int i = 0; i < n; i++){
    string str;
    cin >> str;
    for(int j = 0; j < m; j++){
      arr[i][j] = str[j] - '0';
    }
  }

  queue<pair<int,int>> q;
  q.push({0, 0});

  while(!q.empty()){
    pair<int, int> front = q.front();
    q.pop();
    int moveX[4] = {1, -1, 0, 0 };
    int moveY[4] = {0, 0, 1, -1 };
    for(int i = 0; i < 4; i++){
      int newX = front.first + moveX[i];
      int newY = front.second + moveY[i];
      if(newX < 0 || newX >= n) continue;
      if(newY < 0 || newY >= m) continue;
      if(c[newX][newY] || !arr[newX][newY]) continue;
      c[newX][newY] = true;
      d[newX][newY] = d[front.first][front.second] + 1;
      q.push({newX, newY});
    }
  }

  cout << d[n-1][m-1] << '\n';

  return 0;
}