Graph Traversal (3) 썸네일형 리스트형 111. Grid & Flood Fill 그리드(격자, Grid)는 특수한 형태의 그래프로, $n$차원 좌표공간에 존재하는 점으로 표현되는 정점들과 정점들 사이를 잇는 간선으로 이루어져 있다. $n$은 대체로 $2$이며 가끔씩 $n$이 다른 값인 문제도 존재한다. 또한 점 대신 칸으로 이루어진 그리드가 등장하는 경우도 많은데, 각 칸을 그 중심점으로 바꾸면 정점과 간선으로 이루어진 그리드로 쉽게 변환이 가능하므로 이것은 별로 문제가 되지 않는다. 그리드의 좌표를 인덱스(Index)라고 하는 경우도 많다. 그리드에서 정점 사이를 잇는 간선은 보통 서로 인접한 칸들 사이에는 모두 존재한다. 일반적으로 그리드에서 두 칸이 인접하다는 것은 이렇게 이해할 수 있다: 정점 $\text{A}$의 좌표가 $(a_1, a_2, \ldots, a_n)$이고 정점.. 110. Breadth First Search 너비 우선 탐색(Breadth First Search, BFS)은 노드를 탐색하고, 그 노드와 인접한 노드를 탐색하고, 그 노드들과 인접한 노드를 탐색하는 식으로 탐색을 시작한 노드에서 가까운 노드부터 차례로 탐색을 진행하는 탐색 방법이다. 이전에 탐색한 노드들과 인접해서 이후에 탐색할 예정이지만 아직 탐색하지 않은 노드들을 저장하기 위해 보통 큐가 사용된다. 탐색 과정에서 시작 노드에서 각각의 노드까지의 최단 경로의 길이를 알 수 있게 된다. DFS와 마찬가지로 인접한 노드가 여러 개 있을 경우 문제 상황에 맞게 탐색 순서를 정하면 된다. DFS를 설명한 글에 나온 그래프의 노드 $\text{D}$에서 BFS를 시작하면 BFS는 다음과 같이 진행된다.먼저 노드 $\text{D}$를 방문한다. 노드 $\.. 109. Depth First Search 그래프 탐색(Graph Traversal)은 트리의 탐색과는 다르다. 서브트리와 같은 개념이 그래프에는 존재하지 않는데다 노드들 사이의 경로도 여러 개 존재할 수 있으므로 트리의 탐색 방법을 그래프에 그대로 적용하는 것은 무리이다. 그래서 그래프는 트리와 다른 탐색 방식을 사용하며, 대표적인 방식은 두 가지가 있다.깊이 우선 탐색(Depth First Search)은 노드를 탐색하고 그 노드와 인접한 노드을 차례로 탐색하는 과정을 재귀적으로 반복하는 탐색 방법이다. 현재 노드에서 탐색할 수 있는 노드를 최대한 탐색하는 방식이라고 생각하면 간단하다. 인접한 노드가 여러 개 있을 때 그 노드들의 탐색 순서에 대한 규칙은 따로 없으며 문제 상황에 맞게 정하면 된다.아래와 같은 그래프가 존재할 때 노드 $\te.. 이전 1 다음
