CSE STUDY BLOG

DFS( Depth-First Search ), BFS( Breadth-First Search ) DFS (Depth-First Search, 깊이 우선 탐색)시작 정점을 방문한 후 하나의 인접 정점을 따라 계속 방문.더 이상 방문할 정점이 없으면 되돌아와 다른 정점을 탐색함.재귀 함수나 스택으로 구현 가능 스택의 LIFO(Last In Frist Out)를 고려해서 스택에 담기는 노드의 순서는 다음과 같다.EMPTY18,7,28,7,6,38,7,6,5,48,7,6,58,7,68,7812,912,11,1012,1112EMPTYBFS (Breadth-First Search, 너비 우선 탐색)시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문Queue 사용 (LinkedList로 구현) 큐의..

DFS + Backtracking 을 이용한 구현DFS (Depth-First Search, 깊이 우선 탐색)트리나 그래프를 탐색하는 방식 중 하나한 갈래를 끝까지 파고든 뒤, 막히면 되돌아가서 다른 갈래 탐색재귀 함수나 스택으로 구현 가능백트래킹 (Backtracking)DFS의 일종의 응용 기법어떤 조건을 만족하지 않으면, 그 분기에서 더 이상 탐색하지 않고 되돌아감(백트랙)즉, 가능성이 없는 경로는 일찍 포기함으로써 탐색 효율을 높임 순열/조합은 가능한 모든 경우를 탐색 - > DFS조건(중복 방지, 순서 조건 등)에 맞지 않는 경우를 잘라냄(Pruning) -> Backtracking 관련 문제백준 N과 M 시리즈https://www.acmicpc.net/workbook/view/7315 1...