- 그래프 탐색 - DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)2022년 09월 04일
- 학페
- 작성자
- 2022.09.04.:02
1. DFS
출처 : 위키백과 - https://ko.m.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Depth-First-Search.gif - 임의로 정해진 루트노드로 부터 시작하여, 한 분기를 끝까지 탐색한 후, 다음 분기로 넘어가 탐색을 계속하는 방식
- 재귀함수 또는 스택으로 구현
- 노드 방문 시, 방문 여부를 반드시 기억해야 한다.
DFS 적용 문제
더보기https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
2606번 코드보기
BOJ - 바이러스 (2606번)
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서
hak-fe.tistory.com
2. BFS
출처 : 위키백과 - https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif - 시작 노드에서 인접한 노드부터 탐색하는 탐색 방법
- 주로 최단 경로를 찾을 때 사용한다.
- DFS와 동일하게 방문여부를 반드시 기억해야 한다.
BFS 적용 문제
더보기https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
2718번 코드 보기
BOJ - 미로 탐색 (2178번)
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. ww..
hak-fe.tistory.com
3. DFS와 BFS는 어느 경우에 적용하면 좋은가?
https://foameraserblue.tistory.com/188?category=481823
PS를 하며 느끼는 DFS와 BFS 선택의 기준
알고리즘 문제 풀이를 하며 여러 사람들과 이야기를 나눈적이 있다. 그 중 알고리즘 문제 풀이를 막 시작한 초급자분들이 가장 헷갈려하는 부분이 그래프탐색 문제를 만났을때, 언제 DFS를 선택
foameraserblue.tistory.com
정리가 정말 잘 되어있다.
'Data structure & Algorithm' 카테고리의 다른 글
[알고리즘] 합병정렬 (Merge Sort) (BOJ 2752, C++) (0) 2024.12.13 [정리] 포인터를 사용하는 이유에 대한 개인적인 생각(백준 1920, C++) (0) 2024.11.23 [알고리즘] 버블정렬 (Bubble sort) (0) 2024.11.22 [알고리즘] 삽입정렬 (insertion sort) (0) 2024.11.21 [알고리즘] 선택정렬 (selection sort) (0) 2024.11.20 다음글이전글이전 글이 없습니다.댓글