이상적 데이터로부터의 탈출, 그래프 순회 - 1. DFS

그래프와 그래프 순회

내가 익히 알고 있는 그래프는 가로 축의 값에 따른 세로 값을 표시하는 방식으로 데이터 사이 상관관계를 직관적으로 표현하는 방법이다. 물리시간에도 많이 그렸던 그런 것이다. 그런데 내가 학계를 떠나 있는 동안, 새로운 의미가 포함됐나보다. 언질도 없이 등장한 낯설음과 손으로 풀면 아무것도 아닌 것 같은 문제에 대한 인지부조화로 큰 고민에 빠졌다. 얘는 도대체 왜 등장한 것일까.

사실 수학자나 공학자들의 생각은 너무 뻔하다. 보나마나 문제 해결에 효과적이기에 도입한 것이라고 생각했다. 효용에 대한 이해는 다음 문제다. 사실 물리학이나 수학에서 다루는 자료는 절대적이거나 이상적인 환경에서의 관측이 비일비재하다. 그것은 자료구조 형태에도 해당한다. 이제까지 마주한 선형구조들을 해결하기 위한 알고리즘에서 벗어나, 좀 더 현실에 가까운 문제를 해결하기 위한 방법으로의 접근법이다. 현실의 문제에 접근한다고 해도, 수학은 수학. 연속되고 일정하지 않은 구조를 다룬다고 하더라도, 데이터화 할 수 있도록 정점과 변, 변의 가중치로 문제와 해결값을 구하는 방식을 취한다.

그래프 순회

그래프 순회는 그래프의 각 정점을 주어진 조건에 맞춰 방문하는 방법으로, 문제를 해결하는 방식이다. 연결된 모든 정점을 방문하는 탐구방식이므로, 상황에 주어진 자료가 아래와 같은 그래프 형태로 구현될 수 있으면 권장할만한 알고리즘이다.

이와 같은 그래프는 우리가 직관적으로 결과를 도출하기에는 원활하지만, 컴퓨터가 알아듣기에는 너무 주관적이다. 그래프를 올바르결국게 해석하는 프로그래밍이 되어있지 않다면, 1의 위치가 2보다 왼쪽으로 이동하기만 해도 전혀 다른 값을 도출할지도 모른다. 아무튼, 결국 컴퓨터의 힘을 빌리고 싶은자는 컴퓨터의 언어로 요청하는 수 밖에 없다. 그래프 역시, 아래와 같이 표현해서 전달해줄 필요가 있다.

• 인접행렬형태
  
  위 도표는, 우리와 컴퓨터의 언어 그 사이의 표현 방법이다. 세로축의 숫자(정점)로부터 가로축의 숫자로 변이 이어진 경우는 1, 이어지지 않은 경우는 0으로 표현하였다. 컴퓨터에게 전달할 때는, 2차원 배열 형태로 전달하면 효과적이다.

	graph = [
	[0,1,1,1,0,0,0],
	[0,0,0,0,1,0,0],
	[0,0,0,0,1,0,0],
	[0,0,0,0,0,0,0],
	[0,0,0,0,0,1,1],
	[0,0,0,0,0,0,0],
	[0,0,1,0,0,0,0]
	]

• 인접리스트형태
  인접행렬의 형태는 구현하기 간편하지만, 마치 스택-큐와 해시테이블의 관계처럼 탐색에 그다지 용이하지 않다. 때문에 조금 더 효과적인 접근을 위해서는 딕셔너리 형태를 활용하는 인접리스트로 구현하는 것도 좋다.

	graph = {
	1 : [2,3,4],
	2 : [5],
	3 : [5],
	4 : [],
	5 : [6,7],
	6 : [],
	7 : [3]
	}

그래프 순회 방식

뜬금없는 얘기지만, 공부의 방식에는 크게 두 가지가 있다고 생각한다. 한 분야에 대해서 깊이 파고들어 고등의 지식을 획득하는 것을 목표로 하며, 그 과정에서 얻은 지식을 주변의 관련 분야로 넓혀가는 방법. 그리고, 여러가지 분야에 대해서 탐구하여 공통의 원리와 철학을 도출하고, 끝내 깊은 지식까지 도달하는 방법. 이러한 방법론은 업무처리 방식이나 효율적인 운동법처럼 직관적인 이분화가 가능하다.

그래프를 탐색하는 방법도 마찬가지다. 출발 정점으로부터 가장 먼 정점까지 도달하는 것을 반복하며 탐색하는 방식과 가까운 정점들부터 탐색하는 방식이 있다. 전자를 깊이 우선 탐색 Depth-First Search(DFS)라 하고, 후자를 넓이 우선 탐색 Breadth-First Search(BFS)라 한다.

DFS의 구현

지금부터는 DFS 방식 알고리즘을 파이썬 함수로 구현할 것이다. 방식은 크게 두 가지이다. 하나는 재귀함수구조, 다른 하나는 스택을 이용한 반복구조이다.

재귀함수구조의 DFS함수

# 처음 인자값으로 넣어줄 visited 선언. 순회한 정점을 받는 리스트.
# 함수 안에 선언 시 초기화 되므로 전역변수로 선언
visited = []

# 함수선언
def dfs_recursive(node, visited)
    # 함수의 인자로 받은 정점은 visited에 추가
    visited.append(node)
    
    # 정점이 가리키는 모든 점을 순회
    for adj in graph[node]:
        # 만약 순회하려는 점이 visited안에 없다면(방문한 적이 없다면)
        if adj not in visited:
            # 순회하려는 점을 인자값으로 함수 재실행(더 깊숙히 탐색)
            dfs_recursive(adj, visited)
    # 함수 정점이 가리키는 모든 값을 순회하면 visited 값 반환
    return visited    

재귀함수를 활용한 DFS함수이다. 재귀함수는 '함수f => 결과값'의 구조에서 결과값으로 실행된 함수f 자체를 재차 실행시키는 함수다. 재귀함수를 만들기 위해서는 반복적으로 반환되는 값과 종료조건의 설정이 중요하다. 위의 함수에서 반복되는 값은 dfs_recursive(adj, visited)와 return visited이고, 종료조건은 if adj not in visited에 부합하지 않는, 즉 순회하는 모든 점이 visited에 포함되는 경우이다.

결론부터 말하자면, 피보나치 수열과 같이 return 값 자체의 누적이 있는 경우의 재귀함수는 아니다. 다만, 함수를 실행할 때마다, visited가 의도에 맞게 갱신되므로, 최종 반환하는 visited 값에 모든 재귀의 결과가 담긴다.

실행순서표 (dfs_recursive() = d_r())

스택을 이용한 반복구조의 DFS함수

# 함수선언
def dfs_stack(start):
    # visited 선언, 순회한 정점 저장
    visited = []
    # 인자값으로 넣은 시작점(start)를 리스트에 넣어 스택에 저장
    stack = [start]
    
    # 파이썬의 falsy값에는 0, "", False, None 뿐만 아니라 [],{},()같은 빈 자료형도 포함된다.
    # stack이 참일 경우는 스택 안에 요소가 존재하는 경우다.
    while stack :
        # top 변수로 stack에서 pop한 값을 저장하고 visited에 저장
        top = stack.pop()
        visited.append(top)
        
        # graph에서 top을 키 값으로 밸류(리스트)값 조회 후 순회
        for adj in graph[top]
            # 만약 adj 값이 visited에 저장되지 않은 경우, stack에 차례로 저장.
            if adj not in visited:
                stack.append(adj)
                
    # while문 종료시, visited 반환
    return visited

스택구조를 활용한 DFS함수이다. 핵심은 스택에 차례로 저장하고, 후입선출을 하기 때문에, 방문한 값에 직접 연결된 정점보다도 새로이 획득한 정점을 먼저 순회한다. 때문에 마찬가지로 깊이 우선의 탐색이 이루어진다.

실행순서표

마무리

우리나라 말로는 알겠는데...

그래프 순회 - 2. BFS으로 이어집니다.