항해 99 3주차를 끝내며

    알고리즘을 배운 지 벌써 2주를 넘어서고 있다. 이번 주에는 그래프와 이를 탐색하는 대표적인 방법 2가지, 그리고 트리에 대해서 학습하였다. 이런 기본적인 개념을 모르는 상태에서 그래프 탐색에 관련하여 전혀 감을 잡지 못 하고 있었다. 스택과 큐를 이용해서 DFS와 BFS를 배우고, 후에 재귀함수를 통해 DFS를 구현하는 방법을 배웠다. 

    트리는 그래프와 거의 같지만, 부모 노드와 자식 노드로 구별할 수 있고, 순환 구조를 가지지 않는 등 독특한 특징을 가진다는 것에서 다르다.

 

그래프

 

    여기서의 그래프는 임의의 개수의 node들과 그 node들을 연결하는 edge로 구성된 것이다. 2차원 배열을 통해 각각의 node가 어떤 node와 연결 되었는지를 표기하는 방법과, dictionary 형태를 통해 각각의 node가 어떤 node와 연결되어 있는 지를 표기하는 방법이 대표적인 두가지 방법이다. 

    항해 기간 중에 배운 그래프는 각각의 edge가 연결 여부 그 자체만을 표현했지만, 경우에 따라서 연결 거리 등의 다양한 정보를 담을 수도 있다. 이런 경우에 대해서 다양한 새로운 유형의 문제를 풀어낼 수 있을 것 같다.

    간단히 검색해본 결과, 다익스트라 알고리즘이나 벨먼 포드 알고리즘이 edge가 거리로 주어질 때 최단 거리를 구할 수 있는 알고리즘이었다. 

 

DFS와 BFS

 

    DFS와 BFS는 while문을 이용해 구현하는 방법은 거의 유사하였다. 다만, BFS는 선입선출의 queue를, DFS는 후입선출을 stack을 이용해서 구현한다. 이는 DFS와 BFS가 의미하는 바를 천천히 생각해보면 왜 이런 자료구조를 이용하는 지에 대해서 알 수 있다. DFS는 현재 방문한 node에서 연결되어 있는 node로 탐사의 방향이 이동하고, BFS는 반대로 각각의 node에서 boundary를 넓혀간다는 느낌으로 탐사가 진행된다. 이는 stack에서 현재 node에 연결 된 node를 추가하였을 때 그 연결 된 node들이 탐사에 이용되는 것과, queue에서는 현재 node에서 연결 된 node를 추가하더라도 그 이전에 추가된 node들에 대해서 먼저 탐사가 진행되기 때문에 탐사의 깊이가 바로 깊어지지 않는다. 

 

    이런 특성을 가지는 DFS는 stack이 아니라 재귀함수를 통해서도 구현할 수 있다. 단순하게 생각을 해보면, 재귀함수의 경우 함수가 진행 되는 중간에 또 함수를 호출하고 이런 호출 정보는 stack 메모리에 쌓이는데, stack을 우리가 관리하지 않고 컴퓨터가 관리해주는 것이라고 생각하면 좋을 것이다. 재귀함수를 이용하는 것 자체가 stack 자료구조를 이용하는 것이고, 따라서 BFS는 재귀함수를 통해 구현하는 것은 불가능한 것이다.

import sys
import collections

nodes, edges, root = map(int, sys.stdin.readline().split())
graph = collections.defaultdict(list)
for _ in range(edges):
    edge = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

for i in graph.keys():
    graph[i].sort()

dfs_visited = list()
bfs_visited = list()

stack = list()
stack.append(root)

queue = collections.deque()
queue.append(root)

while stack:
    now = stack.pop()
    if now in dfs_visited:
        continue
    dfs_visited.append(now)
    for link in graph[now][::-1]:
        if link not in dfs_visited:
            stack.append(link)

while queue:
    now = queue.popleft()
    if now in bfs_visited:
        continue
    bfs_visited.append(now)
    for link in graph[now]:
        if link not in bfs_visited:
            queue.append(link)

for i in dfs_visited:
    print(i, end=' ')
print()
for i in bfs_visited:
    print(i, end=' ')

    위 코드는 백준 온라인 저지에서 DFS와 BFS 문제를 풀이한 것이다. Stack과 queue로 이용하는 자료구조가 다르다는 것을 제외하면, 그 형태가 거의 일치함을 볼 수 있다.

 

트리

 

    트리는 그래프와 거의 유사한 형태이지만, 방향성을 가진다는 차이가 존재한다. 마치 나무를 뒤집어 놓은 형태를 가지고 있는데, 루트 노드를 제외한 모든 노드는 부모 노드를 가지고 있고, 자식 노드는 있을 수도 있고 없을 수도 있다. 자식 노드가 없는 노드들의 경우 leaf 노드라고 한다. 또한, 모든 edge는 부모 노드와 자식 노드 사이에만 존재할 수 있고, 따라서 순환 구조가 존재할 수 없다. 트리도 여러가지 종류로 분류할 수 있는데, 대표적인 예시로 각각의 부모 노드가 자식 노드를 최대 2개까지만 가질 수 있는 이진 트리 등이 존재한다. 

 

    이진탐색트리 자료구조를 이용하여 대소관계 비교를 통해 LogN의 시간을 소요하여 자료를 탐색할 수 있고, heap을 이용하여 최대값과 최소값을 이용하는 경우 LogN의 시간을 통해 찾을 수 있다. 이런 LogN의 시간복잡도는 tree의 각 단계 별로 한번 씩 탐사하기 때문에 그런 것이다.