음… ㅋㅋ 면접보고 왔는데 bfs/dfs의 장단점을 물어보셨다. 나는 뭔지만 공부했고 구현해보는 데에만 집중한 나머지 장단점이 뭔지 궁금해하지 않았다는 사실…!😱 그래서 오늘 공부해보려고 한다. BFS의 장단점? 🧐 장점 경로가 여러 개인 경우에도 최적해를 보장한다. 최단 경로가 존재한다면 최적해를 찾을 수 있다. 왜?: 한 노드의 자식들을 모두 탐색하기 때문에. 단점 노드의 수가 많아지면 탐색해야하는 노드의 수도 많아진다. DFS의 장단점? 🧐 장점 최선의 경우 가장 빠름....
음… 나는 탐색알고리즘을 매우 어려워 하는 사람이다…😭😭 이것에 이어서 길찾기를 무서워하는데..😱 프로그래머로서 이런것들은 좀 이겨내야하지 않을까? 라는 생각이 들어서.. 원래 무서운 것은 몰라서 그런거라고 했으니, 나는 이 녀석들을 공부해서 안무서워해야겠다.😋😋😋 Graph(그래프)는 무엇일까? 🧐 BFS, DFS를 알기전에 그래프라는 자료구조를 먼저 알아야한다. 그래프는 정점(V)과 간선(E)들의 집합이다. 간선은 정점과 정점 사이를 직접 연결하는 선을 말한다. G = (V,E)로 수학적으로 표기한다. 💚 그래프의 표현방법 인접 행렬 1 2 3 4 5 6 7 8 9 int V; //정점의 갯수 int E; //간선의 갯수 int[,] Graph = new int[V, V]; //N x N 행렬 for (int i = 0; i < E; i++) { Graph[v1,v2] = 1;//방향 그래프 인접행렬로의 표현 } 인접 리스트 1 2 3 4 5 6 7 8 9 10 11 12 13 int V; //정점의 갯수 int E; //간선의 갯수 List<int>[] Graph = new List<int>[V + 1]; for (int i = 1; i < N + 1; i++) { Graph[i] = new List<int>(); foreach(v in AdjacencyVertices) { Graph[i]....