티스토리 뷰
DFS란?
DFS(깊이 우선 탐색)는 그래프의 시작 노드에서 출발하여 탐색할 할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
DFS의 특징?
- 스택 자료구조를 사용하지만 보통은 스택 성질을 가지는 재귀 함수로 구현한다.
- 재귀함수를 이용하기 때문에 스택 오버플로(시간초과)에 유의해야한다. -> 다음 게시글에 설명할 BFS보다 느리다.
- 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열 필요
DFS의 동작과정
1. DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화
- 인접 리스트 그래프로 표현하기
- 방문 배열 초기화하기
- 시작 노드 스택에 삽입하기
2. 스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입
- pop을 수행해 스택에서 노드를 꺼낸다.
- 꺼낸 노드의 인접 노드들을 스택에 삽입
- 삽입한 노드들 방문 배열에 체크
3. 스택 자료구조에 값이 없을 때까지 반복
- 스택 자료구조에 값이 없어질 때까지 반복
- 이미 다녀간 노드는 재삽입하지 않는 것이 포인트
'CS > Algorithm' 카테고리의 다른 글
[백준, Java] 연결 요소의 개수 구하기 - DFS (0) | 2023.02.09 |
---|
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Iterator Pattern
- 퍼싸드패턴
- 브리지 패턴
- Flutter
- 양방향연관관계
- restapi
- 빌더 패턴
- FacadePattern
- UML 필요성
- springsecurity
- 프록시패턴
- CompositePattern
- 복합체 패턴
- idtoken
- 플라이웨이트패턴
- java문법
- 반복자 패턴
- dfs
- GithubActions
- 프로토타입 패턴
- 컴포지트패턴
- ArrayDeque
- 구글로그인
- 책임연쇄패턴
- 책임체인패턴
- 상태 패턴
- 메멘토 패턴
- jpa
- Chain of Responsibility
- n+1
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
글 보관함