MIT 6006 Lec10 : DFS

D+58

나는 여러 가지를 하고 있다. 건축 소프트웨어 엔지니어라는 타이틀을 가져가면서 내가 나 자신을 위해 배워야 할 것들이 상당히 많아졌다. 지금 행위를 비유하자면 큰 근육을 키우기 위해 주변에 도와주는 근육들을 키우는 중이라고 보면 된다. 그럼 이야기를 써 내려간다

Depth First Search, 깊이 우선 탐색

그래프부터는 상당히 중요하다. BIM을 이루는 요소는 건축물의 속성정보와 형상정보이다. 형상 정보는 컴퓨터 그래픽이라고 불리는 분야이며, 컴퓨터 그래픽은 매쉬를 기본으로 한 그래프로 이루어져 있다. 좀 더 깊이 들어가면 NURBs라고 하는 수학 식으로도 표현되지만 최종적으로 눈에 보이는 형상을 만들기 위해서는 매쉬로 변환되는 과정을 거친다. 

객체 간의 관계도 그래프로 정의된다. BIM에서 핵심이 되는 파일 포맷은 IFC이다. IFC를 열어보면 각 객체 간 관계성을 표시한 것을 볼 수 있다. 그래서 IFC로 무언갈 하기 위해선 그래프를 이용할 줄 알아야 한다. 

그래프를 탐색하는 방법은 깊이 우선 탐색과 지난번에 다룬 너비우선 탐색이 있다. 너비우선탐색은  한 노드로부터 한 단계 떨어진 다음 노드의 집합을 탐색하고 그 노드의 다음노드의 집합을 탐색하며 한 층 씩 쌓아가는 방식이었다. 이와는 다르게 깊이우선 탐색은 한 노드에서 연결된 다음노드로 들어가고 그다음노드로 들어가고 계속 현재 노드가 인접 노드가 없을 때까지 들어간 후 해당 노드에서부터 다시 문제를 해결하면서 올라가는 형식을 취하고 있다. 흔히 backtracking이라고 표현하는 방식이다. 

DFS 코드

코드로 살펴보면 아래와 같다.

인접 노드를 표현한 리스트를 Adj라고 한다. 시작 노드를 s, 지난 방식처럼 parent는 list, order는 list이며, 해당 scope가 어떻게 해결되는지 보여주기 위한 용도이다. 코드를 한 줄씩 읽어보면 다음과 같다

최초에 parent가 없다면 노드의 개수크기의 리스트를 만들어준다. 그리고 s의 parent를 자기 자신으로 설정해 준다. order도 비어있는 리스트로 만들어준다. 

그 후 현재 노드 s의 인접노드 v에 대해서 알고리즘을 수행한다. v의 parent가 없다는 뜻은 아직 v 노드를 방문하지 않았다는 것과 같은 의미이다. 따라서 v는 s의 인접 노드였으니, v의 parent를 s로 설정해 준다. 그 후 v에 대해 dfs를 수행을 진행한다. 이렇게 되면 Adj [s]가 없는 상태까지 계속 dfs가 열리게 된다. Adj [s]가 없을 때 order.append(s)가 작동하고 해당 스코프가 해결되게 된다. 그러면 다시 그전단계의 스코프가 해결되며 order에 노드들이 추가되게 된다.

끝맺으며

그래프부터는 컴퓨터 그래픽이나 건축을 하는 사람들에게 상당히 중요한 부분이다. 나도 누군가를 가르칠 수준은 아니지만 그래도 가르치려고 노력하는 공부가 가장 큰 공부라고 하기에 어떻게든 설명해보려 했다. 내가 쌓아가는 이 과정이 누군가에겐 도움이 되길 바라며 글을 마친다.