BFS2

• 

  [c++] BFS, DFS(너비 우선 탐색. 깊이 우선 탐색) 1. 그래프에서 탐색 알고리즘 문제를 풀다보면 많은 그래프들을 마주하게 된다. 대표적인 예가 미로에서 최단거리를 찾는 문제나 연결되어 있는 컴포넌트를 찾는 문제에서이다. 우리는 이렇게 그려져있거나 가상의 그래프를 탐색해야하는데 컴퓨터는 일정한 알고리즘에 의해 이러한 그래프들을 탐색한다. 그 중 대표적인 예가 DFS(깊이 우선 탐색 Depth-First-Search)와 BFS(Breadth-First-Search 너비 우선 탐색)이다. 2. DFS (깊이 우선 탐색)이란? 그래프가 위와 같이 존재할 때 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색한 후 넘어가는 탐색 방식이다. 위의 그림을 보면 한 번 이동한 줄기의 마지막에 도착할 때까지 그 분기를 탐색한 후 다음 분기로 넘어가는 것을 확인할 수 있다.. c++/알고리즘 2022. 4. 27.

• 

  백준2178번-미로BFS 이 문제는 가중치가 같은 맵 안에서의 최단 경로를 찾는 문제이다. 이는 자료구조 queue를 사용하며 풀면 되는데 나의 코드는 다음과 같다. #include #include #include #include using namespace std; int n, m, y,x; int max = 104; int a[104][104]; int visited[104][104]; // 입력 배열과 방문 배열 int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int main() { cin >> n; cin >> m; for(int i = 0; i >a[i][j]; } }//입력 만들기 queue q; // q.. c++/알고리즘 2022. 3. 28.