나른한코딩_

개념 BFS (Breath First Search) 너비 우선 순회 queue로 구현 (queue를 활용하기 때문에 FIFO) 장점 : 최적해를 찾을 것을 보장한다 ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현 후, 짱구와 철수 사이의 관계 경로를 찾는 경우 BFS : 짱구와 가까운 관계부터 살핀다 DFS : 지구 상 모든 관계를 다 살펴봐야할지도,, 로직 시작 노드를 큐에 삽입하고 방문처리 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리 (방문하면 현재 위치는 pop해주고 방문처리 -> 방문할 곳은 queue에 넣음) DFS (Depth First Search) 깊이 우선 순회 stack과 재귀 함수로 구현 두 노드 사이의 최단 경로 혹..

오늘은 DFS와 BFS의 예제를 구현해보며 로직을 이해해보고자 합니다. DFS와 BFS를 구현하려다보니, 그래프를 먼저 구현하는 해야겠더라구요🤔 그런데 그래프를 어떻게 구현해야할지 몰라서 우선은 하드코딩으로 그래프를 생성한 후, DFS / BFS를 구현해보았습니다. 다음 글에 그래프 구현에 대한 글을 올려두겠습니다 😄 DFS와 BFS의 개념을 간단하게 소개한 후 바로 코드로 넘어가겠습니다. . . . . 그래프를 탐색하는 방법에는 크게 DFS와 BFS가 있습니다. 1. DFS (Depth-First Search) '깊이우선탐색(DFS)'은 가장 깊은 노드까지 내려단 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색을 합니다. root 노드(혹은 다른 임의의 노드)에서 시작하여 다른 branch..