dfs 썸네일형 리스트형 사이클 찾기: DFS 유향 그래프에서 사이클이 있는지 판단하고, 사이클에 포함되는 노드의 개수가 몇 개인지 세는 알고리즘으로 백준 알고리즘 저지의 9466번: 텀 프로젝트 문제가 이에 해당한다. 9466번: 텀 프로젝트 - Baekjoon Online Judge https://www.acmicpc.net/problem/9466 구글링만 해봐도 해당 문제에 대한 많은 풀이가 존재하지만, 아무래도 이런 로직은 내 코드로 정리하는게 제일 이해도 잘가고 나중에 봐도 이해하기 쉬울 것 같아서 풀이 위주로 정리해봤다. 문제에서는 프로젝트를 함께하고 싶은 학생을 선택하는 것이 나오는데 선택은 한명씩 하게 되있으므로, 각 노드에서 나가는 간선은 하나씩이라는 것을 알 수 있다. 주의해야할 것은 자기 자신도 선택할 수 있으므로 나가는 간선이 .. 6. DFS와 BFS 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)는 탐색방법 중 가장 기본이 되는 방식입니다. 이름에 어떠한 방식으로 탐색이 이루어지는지 압축적으로 제시된 것만큼 그 사용목적과 방법이 확실한 알고리즘이라고 할 수 있습니다. DFS는 말그대로 깊이를 우선하여 탐색하는 알고리즘입니다. 만일 격자 모양으로 구성된 하나의 그래프가 주어졌다고 생각해보겠습니다. 중간에 끊김없이 한칸한칸을 모두다 탐색해야한다고 했을 때 우리가 취할 수 있는 방법은 마치 한 손 그림을 그리듯 쭉 타고 가면서 하나씩 노드들을 방문하는 것입니다. 오른쪽으로 쭉타고 가다가 더이상 오른쪽으로 갈 수 없으면 밑으로 그리고 더이상 밑으로 갈 수 없으면 왼쪽으로 또 더이.. 이전 1 다음