[알고리즘 문제 모음] 깊이 우선 탐색 (DFS, Depth First Search)

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.*

★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다.

+가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다.

 

 

일반 DFS 문제

[백준] 텀 프로젝트(9466) - Gold 4

[백준] 빵집(3019) + 그리디 - Gold 2

 

 

DFS를 이용하는 알고리즘의 세부 분류들

 

정말 DFS만을 사용해서 해결하는 간단한 문제들보다는 이를 활용하는 알고리즘을 공부해보자.

 

 

위상정렬 문제 모음

[알고스팟] 고대어 사전(DICTIONARY) + DFS 위상 정렬

[백준] 장난감조립(2637) + 다이나믹 - Gold 2

[백준] 최종 순위(3665)★ + 큐 위상 정렬 - Gold 1

[백준] 알고스팟어(2848)★ + 큐 위상 정렬 - Platium 5

[백준] 임계경로(1948)★ + 임계 경로 (Critical Path) -Platium 5

 

 

오일러 서킷/ 트레일(경로) 문제 모음

[알고스팟] 단어 제한 끝말잇기(WORDCHAIN) - 하

[백준] 철도 여행(18250)★ - Platium 4

 

 

절단점과 절단선 문제

Articulation point, Bridge (Cut vertex, cut edge)

 

 

강결합 컴포넌트(SCC, Strongly Connected Component) 문제

[백준] Strongly Connected Component(2150)★ +타잔 알고리즘- Platium 5

[백준] 축구 전술(3997)★ +타잔 알고리즘 -Platium 4

[백준] MT(10265)★★ + 배낭(knapsack) -Platium 4

 

 

2-SAT (SCC활용)

[2-SAT 해설] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이)

[백준] 2 - SAT - 3(11280)  - Platium 4

[백준] 2 - SAT - 4(11281)★ + 답 출력하기 - Platium 3

[백준] 아이돌(3648)★ - Platium 4

[백준] 호텔 관리(16915) + 식 세우기 -Platium 3