너비 우선탐색 (BFS)란? BFS는 그래프 전체를 탐색하는 방법 중 하나로써 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색합니다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다. 주로 구현은 큐라는 자료에 이웃하는 정점을 다 담아놓고 차례대로 POP을 하는 방식으로 구현합니다. [Algorithm] 자료구조 그래프(Graph)란 무엇인가? BFS의 장점 1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름 3.너비를 우선 탐..
깊이 우선탐색 (DFS)란? DFS는 그래프 전체를 탐색하는 방법중 하나로써 시작점 부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법입니다. 스택이나 재귀함수를 통해서 구현할 수 있는데 재귀함수가 구현이 간편하기에 대부분 재귀함수로 구현하는것 같습니다. 구현시 주의할점은 노드를 방문시 방문 여부를 반드시 검사해야합니다. 그렇지 않다면 무한루프에 빠질 수 있습니다. [Algorithm] 자료구조 그래프(Graph)란 무엇인가? DFS의 장점 1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음 3. 구현이 너비 우선 탐색(BFS) 보다 간단함 DFS의 단점 1. 단순 검색 속도는 너비 우선..
그래프란? 그래프는 정점과 간선으로 이루어진 자료구조입니다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼수도 있겠습니다. 그런면에서 트리는 그래프의 일종인 셈입니다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않습니다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있습니다. 실생활에서 다양한 예를 그래프로 표현할 수 있습니다. 대표적으로 지하철 노선도, 도심의 도로등이 있습니다. 이런식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수 있습니다. 그래프는 알고리즘에서 굉장히 많이 사용됩니다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알..