kruskal-maze

union - find 알고리즘

Forest의 표현방법

Tree(수형도)는 cycle이 없는 연결 단순 그래프이다. 위와 같이 Non-connected인 tree component 들의 묶음을 Forest라 하면 적절한 표현일 것이다. 이와 같은 Forest를 컴퓨터가 다룰 수 있도록 어떻게 표현할 수 있을까?

Forest의 연결상태를 하나의 배열로 나타낼 수 있다. 예를 들어 0~9번까지의 10개의 노드(node 혹은 vertex)가 위와 같이 연결되어 있는 상황을 생각하자. 본래 수형도 자체에는 노드 간의 상하관계나 순서가 없지만 자료구조화시키기 위해서 부모와 자식 노드의 관계를 부여할 필요가 있다. 가장 위에 표시한 노드를 루트(root node)라 하자. 또 연결되어 있는 두 노드에서 위에 있는 노드를 밑의 노드의 부모 노드, 그 반대의 관계를 자식 노드라 하자. 예컨대 3번 노드의 부모는 4번이고, 4번 노드의 부모는 9번이며, 9번의 부모 노드는 없으므로 9번은 루트가 된다. 즉 3번 노드의 루트는 9번이라 할 수 있는 것이다.

이러한 개념을 도입하고 나면 이제 Forest의 상태를 배열 내지는 파이썬에서의 리스트 타입으로 표현하는 것이 가능해진다. 리스트의 n번째(n=0, 1, 2, ...) 위치에 있는 숫자가 n번 노드의 부모를 나타낸다고 정하자. 이때 루트 노드의 경우 부모가 없으므로 그 자신의 번호를 사용하도록 한다.

(함수의 관점으로 보면 배열의 값이 fixed point일 필요충분조건은 해당 번호의 노드가 루트인 것이다.)

이와 같이 규칙을 정하면 위 그림의 Forest는 다음과 같은 배열로 나타내어진다.

[0, 1, 9, 4, 9, 6, 6, 7, 8, 9]

역으로 이 배열에 대응되는 Forest는 그래프적으로 isomorphic함도 쉽게 추론할 수 있다. root를 찾는 과정은 반복문 또는 재귀함수를 이용해서 직선 y=x에 대해 Picard's method와 유사한 방식을 적용하는 것으로 구현할 수 있을 것이다.

Weighted graph의 표현

일반적인 단순 연결 그래프에서 각 edge에 길이 혹은 비용으로 해석될 수 있는 weight가 주어진 것을 Weighted graph라 한다. 앞에서와 마찬가지로 적당한 규칙을 부여하면 이러한 Weighted graph도 파이썬의 리스트를 이용해 표현할 수 있다.

한 edge는 양 끝점과 weight값으로 표현할 수 있으므로 [끝점, 끝점, 길이]의 크기가 3인 리스트들로 이루어진 중첩된 리스트를 생각하자. 예를 들어 3번 노드와 4번 노드를 연결하는 변의 weight가 1이므로 이 edge는 [3, 4, 1]로 나타낼 수 있다. 마찬가지 방법으로 나머지 모든 edge들을 표현하여 하나의 리스트로 묶으면 다음과 같은 리스트를 얻는다.

[[3, 4, 1], [1, 2, 3], [1, 3, 4], [1, 4, 5], [1, 5, 6], 
 [2, 6, 7], [2, 4, 5], [5, 7, 8], [5, 6, 7], [6, 7, 8]]

객체 지향 프로그래밍과 클래스

객제 지향 프로그래밍(Object Oriented Programming, OOP)은 기본적으로 프로그램에서 생성하고 변조하는 등의 작업을 가할 대상들을 규격화시키고 대상에 대해 가능한 작업들을 명시적으로 집합시킴으로써 절차 지향의 방식에 비해 코드의 반복을 줄이고 가독성을 높임으로써 디버깅을 수월하게 하도록 하는 등 여러 이점을 얻고자 하는 프로그래밍 패러다임이다. 실질적으로는 python, java 등 여러 언어에서 클래스를 정의하고 인스턴스를 만들어 클래스 내부에 정의된 메서드를 호출함으로써 실현된다. 클래스는 객체의 명세를 정의하는 코드 묶음인데 대상의 규격과 행위를 정하는 것으로 이해할 수 있다. 이때 규격이란 클래스의 필드, 행위는 메서드에 해당한다.

예를 들어, Person 이라는 클래스에는 name, age, gender 등의 필드가 있을 것이며, 사람이 행하는 동작 - run(), sleep(int time) -과 같은 메서드를 정의할 수 있을 것이다. OOP의 장점은 이렇게 정의한 클래스를 이용해 몇 번이고 다른 Person 인스턴스를 만들어낼 수 있다는 것이다. 또한 상속 기능을 활용하면 개념 사이의 포함관계를 반영하여 의미론적으로 타당한 프로그래밍이 가능하고 코드의 중복도 줄일 수 있다. 모든 학생은 사람이므로 앞의 예시에서 Person을 상속받는 자식 클래스 Student를 생각하면 이는 부모 클래스인 Person이 갖고 있던 필드들과 메서드들을 모두 갖게 되며 Student만 갖는 다른 속성들을 추가하여 정의할 수 있는 것이다.

동적 타입 언어인 파이썬에서는 클래스 선언에서 필드를 명시적으로 선언하지 않는 대신 self 키워드의 속성으로 지정하여 사용한다. 객체의 인스턴스가 만들어질 때 클래스의 생성자 __init__ 함수가 호출되어 해당 객체의 인스턴스 변수(필드)가 초기화(값이 지정)된다.

재귀함수(Recursion)

함수의 선언 내에 자신을 다시 호출하는 함수를 재귀함수라고 한다. 보통 조건문(if) 내에서 재귀호출이 이루어지고 조건문의 다른 분기에서 종결되는 구조를 갖는데, 이는 일반적인 함수에서 while 등의 반복문을 사용하는 것과 동일한 효과를 갖는 것으로 이해할 수 있다.

크루스컬 알고리즘

최소 생성수형도(Minimal spanning tree)를 찾는 알고리즘이다. weight가 작은 edge부터 cycle이 생기지 않도록 추가하는 방식으로 구현한다.

함수형 프로그래밍과 람다식

객체 지향의 방식에서 인스턴스를 만드는 것은 기본적으로 메모리에 부담을 주는 일이다. 프로그래밍에서 때로는 객체의 구조나 자료형, context에 관계없이 특정(주로 단순한) 역할을 맡기고 클래스의 메서드를 실행시킬 때와는 다르게 본래의 값이 변조될 걱정을 전혀 하지 않아도 되는, 수학적인 의미에 더 가까운 순수한 '함수'가 필요한 경우가 있다. 이러한 pure function을 주로 이용해 프로그램을 설계하는 것을 함수형 프로그래밍(Functional Programming)이라고 한다. 정렬에 사용될 key로 사용하기 위해 리스트에서 특정 인덱스를 지목하는 등의 작업에는 주로 그 자리에서 익명으로 함수를 만들어 사용하는 경우가 많은데, 이를 람다함수라고 한다. 예를 들어 다음 람다식은 x가 주어질 때 1을 더해 반환하는 익명함수를 정의하고 있다.

lambda x: x + 1

그래프의 꼭짓점 개수 찾기

주어진 그래프의 꼭짓점의 개수가 v이면 생성수형도의 변의 개수는 v-1가 됨을 이용하려고 한다. 하지만 위의 방식대로 표기한 Weighted graph에서 바로 꼭짓점의 개수를 확인할 수는 없다. 물론 kruskal 함수에서 꼭짓점의 개수를 parameter로 받으면 되겠지만 알고리즘의 완결성을 위해 graph로부터 그 값을 추출하여 사용하도록 하자. 이를 위해 파이썬에서 기본으로 제공하는 집합 자료형을 사용하여 graph 표현에서 등장하는 모든 노드의 번호를 집합에 추가하면 중복이 제거되어 그 원소의 개수가 꼭짓점의 개수와 같을 것이다.

s = set(i[0] for i in graph)
s.update(i[1] for i in graph)
nodenum = len(s)

미로 만들기

미로의 코드화

가장 간단한 형태의 미로를 생각해보자.

s ? |
?   ?
| ? e

s에서 출발해서 e에 도달하는 미로를 만들기 위해서는 ?로 표시된 4개의 길목을 열어주어야 한다. 이 경우는 두 가지 자명한 방법만 존재한다. 이렇게 미로를 표현하는 것을 임의의 크기에서도 적용할 수 있도록 일반화하기 위해 각 셀의 값이 0, 1, 2인 matrix를 도입하여 코드화하자.

• 꼭짓점 : (짝수, 짝수) = 1 : nodes

• 빈 공간 : (홀수, 홀수) = 0

• 예비 선분 : (짝수, 홀수) = (홀수, 짝수) = 2 : edges

위의 미로꼴은 다음과 같은 표현을 갖게 된다.

[[1 2 1]
 [2 0 2]
 [1 2 1]]

이와 같은 표현을 (3, 3) 규격의 기본형이라고 하자. 이를 바탕으로 일반적인 크기의 미로로 확장시킬 수 있다.

가로로 한 단위를 연장시킨 경우: (5, 3) 규격의 기본형
[[1 2 1 2 1]
 [2 0 2 0 2]
 [1 2 1 2 1]]

가로, 세로 각각 한 단위씩 연장시킨 경우: (5, 5) 규격의 기본형
[[1 2 1 2 1]
 [2 0 2 0 2]
 [1 2 1 2 1]
 [2 0 2 0 2]
 [1 2 1 2 1]]

초기 세팅

우리는 임의의 크기를 입력받아 행렬로 미로를 표기하려고 한다. 이를 위해서는 미로의 규격을 어떻게 정할 것인지를 확정해야 할 것이다. 먼저 바둑판 모양의 그래프를 생각하자. 가로줄과 세로줄이 만나는 모든 지점을 꼭짓점으로 하고 상하좌우로 이웃한 두 꼭짓점을 잇는 선분 하나하나를 서로 다른 변으로 취급하자.

앞에서 간단한 경우의 예시로부터 다음 2x2 행렬행렬을 가로, 세로로 반복해서 이어붙인 형태만 기본형이 되는 것을 알 수 있다.

[[1 2]
 [2 0]]

이 행렬을 연속해서 붙인 뒤 마지막 행과 열을 제거하면 특정 규격의 기본형을 얻을 수 있게 된다.

알고리즘 개요

미로의 규칙에 따라 상하좌우로 인접한 꼭짓점끼리만 선분을 연결할 수 있다. 0은 고정된 벽이다. 1을 vertex로 보자. 2는 확정되지 않은 edge이다. 처음에는 상하좌우로 모두 2로 연결되어 있는 상태이다. 이 상태에서 적당히 연결을 지워서 (0,0)에서 (n,n)으로 가는 유일한 경로를 만들 수 있으면 미로의 정의에 부합한다. 이는 주어진 꼭짓점들을 모두 잇는 spanning tree를 건설하는 것으로 실현할 수 있다. 그래프의 모든 선분의 weight가 같다고 간주하고 mininal spanning tree를 찾는 kruskal의 알고리즘을 적용하자. 모든 선분의 weight가 같기 때문에 임의의 순서로 연결할 수 있다.

• 2를 0으로 바꾸는 것은 연결을 지우는 것으로 해석한다.
• 2를 1로 바꾸는 것은 상하 또는 좌우에 있던 기존의 꼭짓점(node) 사이의 연결을 확정하는 것으로 해석한다.

검사할 edge에 인접한 node가 이미 연결되어 있으면(union-find 알고리즘 사용) 해당 edge를 0으로 확정, 그렇지 않으면 1로 확정한다. 매번 unique한 미로를 얻고자 한다면 검사할 edge의 리스트를 무작위로 섞어주는 과정이 필요할 것이다.