Algorithm&DataStructure - BFS

Algorithm&DataStructure - BFS

1 BFS

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

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

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

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

2 백준 2178번: 미로탐색

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

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

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

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

#include #include #include #include using namespace std; int dir[4] = {0,1,0,-1}; class Maze{ private: vector> map; vector> visited; vector> movements; int width; int height; public: Maze(int height, int width):width(width), height(height){ vector tmp2(width, 0); for(int i = 0; i tmp(width,false); visited.push_back(tmp); string input; cin>>input; for(int j = 0; j> 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>height>>width; Maze maze(height, width); cout<

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

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

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

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

from http://jsdysw.tistory.com/120 by ccl(A) rewrite - 2021-08-02 19:26:33