1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | struct Node { public bool check; public List<int> neighbor; } static void DFS(ref Node[] tree, int start) { Console.Write((start+1) + " "); tree[start].check = true; for(int i =0; i<tree[start].neighbor.Count; i++) { if(tree[tree[start].neighbor[i]].check == false) { DFS(ref tree, tree[start].neighbor[i]); } } } static void BFS(ref Node[] tree, int start) { Queue<int> que = new Queue<int>(); que.Enqueue(start); while(que.Count > 0) { int check = que.Dequeue(); tree[check].check = true; Console.Write((check + 1) + " "); for (int i = 0; i < tree[check].neighbor.Count; i++) { if(tree[tree[check].neighbor[i]].check == false) { //Console.WriteLine("???"); que.Enqueue(tree[check].neighbor[i]); tree[tree[check].neighbor[i]].check = true; } } } } | cs |
백준 1260번 풀면서 DFS와 BFS의 개념에 대해서 배웠는데 그 개념을 바탕으로 한번 만들어 본 함수이다. 사용할 때 "Node[] tree = new Node[zum];"를 선언해주고 해야한다. 그리고 각 노드안의 리스트를 정렬해주는 것도 빼먹으면 안되고.
DFS는 깊이 우선 탐색으로 재귀적으로 가장 맨 앞에 있는 노드에 들어가서 다시 그 함수를 호출하고 하는 식으로 가장 우선 노드쪽으로 쭈우우욱 들어갔다가 그 다음길로 들어가는 방식이다.
BFS는 넓이 우선 탐색으로 가장 위의 노드에서 모든 가지 노드에 다 들어가서 확인하고 그 다음에 각 노드들의 가지에 들어가서 확인하는 식으로 싹 도는 형식이다.
중앙대 예술공학과 홍진호