너비 우선 탐색2 [백준 C++] 16946번: 벽 부수고 이동하기 4 1. 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 3. 소스 코드 #include #include #include #include #define MAX_N 1000 #define MAX_M 1000 using namespace std; int N, M; int dy[4] = {-1, 0, 1, 0}; int dx[4] = { 0, 1, 0.. 2024. 4. 14. [알고리즘] BFS(너비 우선 탐색) 1. Breadth First Search (BFS, 너비 우선 탐색1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 시작점에서 가까운 점부터 탐색하는 방식 - 개미굴에 물을 부어서 물이 점점 안 쪽으로 스며들어가는 방식과 비슷하다. 2. 장점1) 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다. 3. 단점1) 경로가 매우 길 경우에는 탐색 기지가 급격히 증가하여 많은 기억 공간을 필요로 한다. 4. 구현Queue를 통해 구현아래 3가지 구조로 나눌 수 있다.1) 시작점 셋팅2) 현재 방문 노드를 Queue에서 pop하기3) 다음으로 방문할 노드 Queue에 삽입#include #include #include ;using namespace std;bool visited[11];v.. 2024. 4. 3. 이전 1 다음
