Algorithm/H. Trees & Graphs (33) 썸네일형 리스트형 113. Diameter of Tree 트리의 지름은 다음과 같이 정의된다. 트리에 존재하는 임의의 정점 $u$와 $v$에 대해, 두 정점 사이에는 항상 한 개의 단순 경로가 존재하며 이 단순 경로의 길이를 정점 $u$와 $v$ 사이의 거리(Distance)라고 한다. 트리의 한 정점 $u$과 임의의 정점 $v$에 대해, 정점 $u$와 $v$ 사이의 거리의 최대값을 정점 $u$에서의 이심률(Eccentricity)이라고 한다. 트리의 각 정점에서의 이심률의 최소값을 트리의 반지름(Radius of Tree)이라고 하고 이심률의 최대값을 트리의 지름(Diameter of Tree)이라고 한다. 쉽게 말해서 트리의 지름은 트리에 존재하는 두 정점 사이의 거리의 최대값과 같다. 다음과 같은 트리에서 지름은 $4$, 반지름은 $2$이다. 간선에 가중.. 112. Bipartite Graph 음이 아닌 정수 $k$에 대해 그래프가 다음 조건을 만족하면 그 그래프를 $k$분 그래프(${\color{#FF0000}k}$-partite Graph)라고 한다. 정점을 $k$개의 그룹으로 분리했을 때 간선으로 직접 연결된 두 정점이 항상 서로 다른 그룹에 속하게 할 수 있다. 이중 $k = 2$일 때 조건을 만족하는 그래프를 이분 그래프(Bipartite Graph)라고 한다. 이분 그래프에 존재하는 모든 사이클은 길이(사이클에 포함된 정점의 수)가 짝수이며, 그 역도 성립한다. 모든 트리는 이분 그래프이다. 어떤 그래프가 이분 그래프인지 확인하는 방법은 간단한데, 임의의 정점에서 DFS를 시작해서 인접한 정점을 탐색할 때마다 그 정점을 이전 정점과 다른 그룹에 추가한 다음 DFS가 끝났을 때 간선이.. 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 그래프의 탐색 방법은 트리의 탐색과는 다르다. 서브트리와 같은 개념이 그래프에는 존재하지 않는데다 노드들 사이의 경로도 여러 개 존재할 수 있으므로 트리의 탐색 방법을 그래프에 그대로 적용하는 것은 무리이다. 그래서 그래프는 트리와 다른 탐색 방식을 사용하며, 대표적인 방식은 두 가지가 있다. 깊이 우선 탐색(Depth First Search)은 노드를 탐색하고 그 노드와 인접한 노드을 차례로 탐색하는 과정을 재귀적으로 반복하는 탐색 방법이다. 현재 노드에서 탐색할 수 있는 노드를 최대한 탐색하는 방식이라고 생각하면 간단하다. 인접한 노드가 여러 개 있을 때 그 노드들의 탐색 순서에 대한 규칙은 따로 없으며 문제 상황에 맞게 정하면 된다. 아래와 같은 그래프가 존재할 때 노드 $\text{A}$에서 DF.. 108. Postorder Traversal 트리의 후위 순회(Postorder Traversal)는 노드의 서브트리를 차례로 방문한 다음 노드를 마지막으로 방문하는 순회 방법이다. 트리의 전위 순회, 중위 순회, 후위 순회 결과 중 두 가지를 알면 나머지 한 가지 순회 결과도 알아낼 수 있다. 앞에서 설명한 트리의 후위 순회 결과는 다음과 같다. $\text{I F B G A J C H E D}$ 구현은 다음과 같다. // 인접 리스트를 사용한 경우 #import using namespace std; vectorv, e[100005]; void postorder_traversal(int prev, int node) { for(auto &p: e[node])if(p != prev)postorder_traversal(p); v.push_back(no.. 107. Inorder Traversal 트리의 중위 순회(Inorder Traversal)는 노드의 왼쪽 서브트리를 먼저 방문한 다음 노드를 방문하고 노드의 오른쪽 서브트리들을 방문하는 순회 방법이다. 여기서 서브트리의 방향에 대한 내용이 등장하는데 이 방향은 단순히 트리의 구조를 나타내었을 때의 방향이라고 생각해도 무방하다. 만약 자식 노드가 $3$개 이상일 경우 서브트리들 중 하나를 왼쪽 서브트리로, 나머지를 오른쪽 서브트리로 간주한다. 하지만 그런 노드가 있는 트리에서는 서브트리의 방향이 별로 의미 없는 경우가 많기 때문에 일반적으로 중위 순회는 이진 트리에서 수행된다. 앞에서 설명한 트리의 중위 순회 결과는 다음과 같다. $\text{I G B F D A E J C H}$ 구현은 다음과 같다. // 인접 리스트를 사용한 경우 #impo.. 106. Preorder Traversal 트리의 순회(Tree Traversal)는 루트 있는 트리에 존재하는 각각의 노드를 일정한 규칙에 따라 한 번씩 방문하는 과정을 의미한다. 일반적으로 트리의 순회는 모든 노드가 최대 두 개의 자식 노드를 갖는 이진 트리(Binary Tree) 구조에서 다루어지지만, 이진 트리가 아닌 트리에서도 순회를 할 수 있다. 순회는 루트 노드에서 시작하며 자식 노드에는 순서가 있다고 가정한다. 노드를 방문하는 규칙은 크게 세 가지가 있으며 규칙에 따라 트리 순회의 이름도 달라진다. 트리의 전위 순회(Preorder Traversal)는 노드를 먼저 방문하고 각각의 자식 노드를 루트로 하는 서브트리를 차례로 방문하는 순회 방법이다. 다음과 같은 트리가 있을 때 전위 순회는 다음과 같은 순서로 진행된다. 루트 노드 $.. 이전 1 2 3 4 5 다음
