728x90
1. 깊이 우선 탐색
- DFS(depth-first search)는 그래프 완전 탐색 기법 중 하나이다.
- 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하고 최대 깊이까지 탐색하는 과정을 반복한다.
- 재귀 함수로 구현한다.
- 스택을 이용한다.
- 시간 복잡도는 O(노드 수 + 엣지 수)이다.
- 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 문제에 사용할 수 있다.
2. 깊이 우선 탐색 과정
DFS를 위해 필요한 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드를 스택에 삽입하기이다.
위와 같이 초기 작업을 끝냈으면 스택에서 노드를 꺼내고 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.
스택에 있는 1을 꺼내고 1의 인접 노드인 2, 3을 스택에 추가했다.
또한 2, 3을 방문 배열에서 T로 바꾼다.
스택에서 꺼낸 노드가 인접 노드가 없는 경우 스택 삽입 연산은 일어나지 않는다.
인접 노드를 스택에 추가할 때 이미 방문한 노드이면 마찬가지로 스택 삽입 연산은 일어나지 않는다.
위와 같은 과정을 스택이 빌 때까지 반복한다.
3. 예제 문제
[11724] 연결 요소의 개수 (JAVA)
# 문제 설명 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0
spicyrisotto.tistory.com
[2606] 바이러스 (JAVA)
# 문제 설명 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-9 이진 탐색 (0) | 2024.03.29 |
|---|---|
| Day-8 너비 우선 탐색 BFS (0) | 2024.03.29 |
| Day-7 계수 정렬 (0) | 2024.03.27 |
| Day-7 기수 정렬 (0) | 2024.03.27 |
| Day-7 병합 정렬 (0) | 2024.03.27 |
