목차
🔔 깊이 우선 탐색 (DFS)
• 재귀 함수, 스택 → LIFO
• 시간 복잡도 : O(V+E)
핵심 이론
- 인접 리스트 & 방문 배열
- 재귀 + 백트래킹
문제 유형
- 단절점 찾기
- 단절선 찾기
- 사이클 찾기
- 위상 정렬
- 연결 요소 개수 / 재귀 깊이 (= DFS 수행 횟수)
- 순열 / 조합
DFS 구현 메소드 - 재귀 함수 사용
public static void DFS(int node) {
// 1) 종료 조건 : 현재 노드가 이미 방문한 노드인 경우
if(visited[node]) return;
// 현재 연결 노드 中 방문하지 않은 노드인 경우
visited[node] = true;
// 2) 재귀
for(int i : A[i]) {
if(!visited[i]) {
DFS(i);
}
}
}
🔔 너비 우선 탐색 (BFS)
• 큐 → FIFO
• 시간 복잡도 : O(V+E)
핵심 이론
- 인접 리스트 & 방문 배열
- 큐에서 노드 꺼내고, 인접 노드를 큐에 삽입하면서 방문 배열 체크
- 배열에 값을 저장하며 해결 가능한 경우 多
문제 유형
- 최단 경로 탐색 (최단 경로 저장할 int형 배열 필요)
BFS 구현 메소드 - 큐 사용
public static void BFS(int node) {
visited[node] = true;
Queue<Integer> q = new LinkedList<>();
q.add(node);
while(!q.isEmpty()) {
int now_node = q.poll();
for(int i : A[now_node]) {
if(!visited[i]) {
visited[i] = true;
q.add(i);
}
}
}
}
(참고)
▷ 대표 예제
[백준/JAVA] 1260번: DFS와 BFS
🔺 문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주
bono039.tistory.com
▷ 인접 행렬 사용 방법
그래프 표현 (인접 리스트 / 인접 행렬)
정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 처음부터 읽어나가면서 각 원소를 일일이 확인 - 인접 행렬은은 정점 u, v가 주어졌을 때, 단 한 번의 배열의 접근으로 연결 여부 확인 공간
zoosso.tistory.com
[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)
그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 행
born2bedeveloper.tistory.com
[Java] 그래프를 탐색하기 위한 인접 행렬과 인접 리스트
[Java] 그래프를 탐색하기 위한 인접 행렬과 인접 리스트
velog.io
▷ 최고의 DFS / BFS 글이라고 생각함....👍👍
PS를 하며 느끼는 DFS와 BFS 선택의 기준
알고리즘 문제 풀이를 하며 여러 사람들과 이야기를 나눈적이 있다. 그 중 알고리즘 문제 풀이를 막 시작한 초급자분들이 가장 헷갈려하는 부분이 그래프탐색 문제를 만났을때, 언제 DFS를 선택
foameraserblue.tistory.com
'코테 > 알고리즘' 카테고리의 다른 글
최단 경로 탐색 알고리즘 (0) | 2023.06.23 |
---|---|
다익스트라 (0) | 2023.06.23 |
위상 정렬 (0) | 2023.06.23 |
시간 복잡도 면에서 좋은 정렬 방법 (0) | 2023.06.14 |
DP (0) | 2023.05.29 |