클라우드 낚시꾼

그래프란? 그래프는 문제 또는 구조를 시각적으로 표현하기 위해 널리 사용되는 자료구조이다. 지하철 노선도와 SNS 관계망이 대표적인 그래프 활용 예시이다. 그래프는 어떻게 구성되어 있을까? 그래프는 정점과 간선으로 구성된다. 정점(vertex, node)은 그래프에서 표현하고자 하는 항목을 의미하고, 간선(edge)는 두 정점 사이의 관계를 의미한다. 두 정점이 간선으로 연결되어 있다면 인접(adjacent)하다고 한다. 서울 지하철 노선도를 그래프 관점으로 해석해보면 다음과 같다. 지하철 노선도에서 각 지하철 역은 그래프에서 표현하고자 하는 항목이기에 정점이 된다. 각 정점(지하철 역)을 이어주는 노선은 1호선, 2호선, 3호선.. 이라는 정점 사이의 관계를 형성하기에 그래프의 간선이 된다. 특히, 홍..

BFS를 쉽게 말하자면? 위 그래프의 시작 노드는 1 이고, 숫자가 낮은 노드부터 탐색한다고 가정하자. 이 가정 아래, 그래프를 가장 가까운 노드부터 탐색하면 1 -> 2 -> 3 -> 5 -> 4 -> 6 라는 결과를 얻을 수 있다. 이것이 BFS이다. BFS의 가장 주요한 모토는 "그래프를 가까운 노드부터 탐색하자." 라는 것을 잊지 말자! BFS 알고리즘 먼저, BFS를 구현하기 위해서는 FIFO 구조인 큐(Queue) 자료구조를 사용해야 한다. 인접한 노드를 반복적으로 큐에 넣게되면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한 동작방식은 아래와 같다. 1) 탐색 시작 노드를 Queue에 Enqueue 하고 방문 처리한다. 2) Front..