그래프 알고리즘 중에 깊이 우선 탐색(DFS) 과정을 유니티로 구현해봤다.
깊이 우선 탐색은 먼저 해당하는 모든 정점을 탐색하고, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 인접 노드를 먼저 탐색하고 인접 노드를 모두 방문하면 그다음 정점으로 탐색한다.
알파벳 박스들은 정점, 보라 색선은 간선이다. Clear 버튼을 누르면 데이터를 가지고 있는 컨테이너들을 비워주고 위치 또한 다시 랜덤으로 설정하도록 했다.
오른쪽에 긴 사각형이 stack으로 실제 정점데이터가 stack으로 push 또는 pop 되면, 정점에 해당하는 이미지박스 역시 채워지고 비워진다.
노란색으로 바뀌는 박스는 stack에 들어있는 정점이고, 파란색은 방문한 정점이다. (방문한 정점은 다시 방문하지 않음)
| 이진트리/AVL트리 유니티_구현 (0) | 2019.04.22 |
|---|
트리 알고리즘을 공부하다 보니까
공부한것을 이용해 보고싶다는 생각이 들었다.
그래서 유니티로 트리구조를 가시적으로 보이도록 구현해봤다.
이진트리와 AVL 트리를 구현했다.
둘다 기본적인 구조는 이진트리이다.
삽입된 노드는 root노드부터 비교하면서 자신의 값보다 현재
위치한 노드가 크면 왼쪽 삽입된 노드가 크면 오른쪽으로 이동한다.
트리의 균형도가 절대 값1이 넘어 갈 경우 자동으로 균형 회전을 하도록 구현했다.
콘솔로만 구현하기는 인터넷에도 많고 구현도 잘되어 있다. 트리구조에 따라 UI오브젝트도 움직이는 이려면 추가적으로 자료구조 구현이 필요하다.
사실 실제 데이터가 움직이는 트리구조와 이미지박스가 움직이는 것은 아예 상관이 없이 움직인다고 생각하면 된다. 별도로 움직여야 한다.
내가 구현한 코드에 노드는 Key는 int비교를 하기 위한 변수로 사용하고
Value는 오브젝트를 움직이기 위한 변수를 같이 담고 있다. (키 값을 통해 오브젝트를 불러오기 위함)
먼저 오브젝트의 위치를 움직여주고 그 다음에 트리구조에 데이터 구조를 변경하도록 한다.
| 그래프 알고리즘 유니티_구현 (0) | 2019.04.27 |
|---|