Algorithm&DataStructure - BFS

1 BFS

- 그래프를 순회(하나의 정점에서 시작해서 차례대로 모든 정점들을 한 번씩 방문) 하는 알고리즘 중 하나

- 한 정점에서 가까운 점들을 우선적으로 탐색, 따라서 시작점에서 도착점까지의 최단거리를 보장해준다.

- 탐색 시 어떤 노드에 대해서 방문을 했는지 안 했는지를 알고 있어야 한다.

- 큐를 활용해서 구현한다.

2 백준 2178번: 미로탐색

- N×M크기의 배열로 표현되는 미로가 있다.

- 0은 벽을 나타내고 1은 이동할 수 있는 칸이다.

- 상하좌우로만 이동이 가능하다.

- (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하라.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int dir[4] = {0,1,0,-1};

class Maze{
private:
  vector<vector<bool>> map;
  vector<vector<bool>> visited;
  vector<vector<int>> movements;
  int width;
  int height;
public:
	Maze(int height, int width):width(width), height(height){
      vector<int> tmp2(width, 0);
	  for(int i = 0; i<height; i++){
     	 vector<bool> tmp(width,false);
      	 visited.push_back(tmp);
      	 string input;
         cin>>input;
      	for(int j = 0; j<width; j++){
          if(input[j] == '1'){
            tmp[j] = true;
          }
        }
        map.push_back(tmp);
        movements.push_back(tmp2);
	  }
  }
  int FindShortestPath(){
    bfs();
    return movements[height-1][width-1];
  }
  void bfs(){
    queue<pair<int,int>> que;
    que.push(make_pair(0,0));
    visited[0][0] = true;
    movements[0][0] = 1;

    while(!que.empty()){
      int row = que.front().first;
      int col = que.front().second;
      for(int i = 0; i<4; i++){
        int next_row = row + dir[3-i];
        int next_col = col + dir[i];
        if(0<= next_row && next_row < height && 0<=next_col && next_col<width && !visited[next_row][next_col] && map[next_row][next_col]){
          que.push(make_pair(next_row,next_col));
          visited[next_row][next_col] = true;
          movements[next_row][next_col] = movements[row][col]+1;
        }
      }
      que.pop();
    }
  }
};

int main(){
  int width, height;
  cin>>height>>width;
  Maze maze(height, width);
  cout<<maze.FindShortestPath();
}

- movements[i][j]는 (i,j)에 도착하는데 걸린 이동 수를 저장하고 있다.

1. 출발위치에서 이동가능한 모든 위치를 먼저 탐색하여 큐에 차례로 집어넣는다.

2. 출발 위치가 큐에서 나온다.

3. 큐에 있는 위치들을 시작점으로 해서 1~2를 반복한다.