DFS
-
BOJ 13023 : ABCDE백준 문제풀이/GRAPH 2020. 5. 15. 17:59
문제 문제 풀어보기 풀이 문제를 이해하는데 좀 오래 걸렸네요... 이 문제는 A -> B -> C -> D 처럼 친구의 친구의 꼬리를 4번 무는 경우를 찾는 겁니다. 그래서 DFS 를 사용해서 깊이가 4가 되는 경우를 찾으면 됩니다. 코드 #include #include #define max 2000 using namespace std; bool check[max + 1]; vector v[max + 1]; // max+1 개의 벡터 생성 int n, m; void dfs(int st, int index) { check[st] = true; // 깊이가 4인경우 종료 if (index == 4) { cout n >> m; for (int i = 0; i >..
-
[Graph] BOJ 1260 : DFS 와 BFS백준 문제풀이/GRAPH 2019. 7. 22. 06:03
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과..
-
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)프로그래밍/알고리즘 2019. 5. 23. 11:51
Goal 깊이 우선 탐색(DFS, Depth-First Search)의 개념 깊이 우선 탐색(DFS, Depth-First Search)의 특징 깊이 우선 탐색(DFS, Depth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 미로를 탐색하는 ..