접근
- graph 또는 tree를 탐색하는 알고리즘이다.
- 특정 노드부터 시작하여 인접한 노드들을 먼저 탐색한다. (최단 경로를 찾을 때 사용)
- 특정 노드로부터의 거리에 따라 순서대로 탐색한다.
알고리즘
- 큐(queue)와 while문을 사용한다.
- 큐(queue)에서 꺼낼 때, 그 노드를 visit 했다고 표시한다.
- 큐(queue)에서 꺼낸 노드와 인접한 노드들을 큐(queue)에 집어넣는다.
- 큐(queue)가 empty상태가 될 때까지 수행한다.
Pseudo-code
while(!queue.empty){
current = queue.pop;
current.visited = true;
for(current.adj)
if(!adj.visited)
queue.push(adj);
}적용
[programmers] Lv.3 경주로 건설(c++)
더보기 #include #include #include #include using namespace std; struct Node{ int x, y; int cost; int dir; Node(int x=0, int y=0, int cost=0, int dir=4) : x{x}, y{y}, cost{cost}, dir{dir}{} }; int so..
jolly-note.tistory.com
https://jolly-note.tistory.com/41
[programmers] Lv.4 동굴 탐험(c++)
4단계는 어려운거같다... 코드를 봐도 cycle을 의미한다하여 응? 왜 그게 cycle을 의미하는건데? 근본적인 질문이 떠오르고 내 방식대로 하려하면 왠지 너무 복잡해진다. 근데 대부분의 답은 내 방
jolly-note.tistory.com
https://jolly-note.tistory.com/43
[programmers] Lv.2 카카오프렌즈 컬러링북(c++)
더보기 #include #include using namespace std; vector > visit; int nb_area; vector x_dir; vector y_dir; int find_area(int i, int j, vector > picture){ nb_area++; queue > que; que.push({i, j}); visit[..
jolly-note.tistory.com
https://jolly-note.tistory.com/69
[programmers] Lv.2 타겟 넘버(c++)
DFS, BFS 두 방법으로 풀었다. (BFS는 나중에 추가 예정) my full code #include using namespace std; int answer=0; void dfs(vector & numbers, int& target, int idx, int num){ if(idx+1 == numbers.size()+1..
jolly-note.tistory.com
https://jolly-note.tistory.com/71?category=1025701
[백준/baekjoon] Silver1 2667. 단지번호붙이기
DFS 연습용으로 들어갔는데 예전에 BFS로 풀었던 것이랑 비슷한 문제(👇)여서 https://jolly-note.tistory.com/43 visit; int nb_area; vector x_dir; vector y_dir; int find_area(int i, int j, vector > pictur..
jolly-note.tistory.com
참고
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
'note > algorithm' 카테고리의 다른 글
| DFS (Depth First Search, 깊이 우선 탐색) (0) | 2022.05.22 |
|---|---|
| linked list - 이중(doubly) 연결 리스트(c++) (0) | 2022.04.27 |
댓글