깊이우선탐색
-
[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 5. 02:12
알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다. 어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다. 그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 대표적인 그래프 탐색 알고리즘 중 하나다. 직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다. BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..
-
[백준 BOJ/C++] 9466 텀 프로젝트알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 23. 23:20
9466번: 텀 프로젝트 그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다. 제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다. 학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다. 그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다. 팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다. 문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다. 중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되..