눈물보다 땀을

특징

- 벽이 중간 중간 끊어진 형태라면 길을 찾지 못한다.

- 오른손으로 오른쪽 벽을 짚으면서 길을 찾는다.

- 오른쪽에 짚히는 벽이 없다면 오른쪽으로 간다.

- 순환구조가 아니라면 사용 가능하다.

Flow

샘플 프로젝트

c++

c#

참고

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 유니티로 만드는 mmorpg 게임 개발 시리즈] part3 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

DFS 

개념

- 깊이 우선 탐색 (Depth First Search)

- 더 이상 정점을 찾지 못할 때까지 정점을 타고 들어가고, 더이상 찾을 정점이 없으면 이전 위치로 복귀해서 또다른 정점을 찾는다.

- 재귀로 구현 가능하다.

리스트를 이용한 구현

        List<int>[] nodes = new List<int>[]
        {
            new List<int>() { 1, 3},
            new List<int>() { 0, 2, 3},
            new List<int>() { 1 },
            new List<int>() { 0, 1},
            new List<int>() { 5 },
            new List<int>() { 4 },
        };

        bool[] visited = new bool[6];
       
        public void DFSByList(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고.

            foreach (int next in nodes[now])   // 연결되어 있는 정점이 아니면 패스.
            {
                // 방문한 정점이면 패스.
                if (visited[next])
                {
                    continue;
                }

                DFSByList(next);
            }
        }

행렬을 이용한 구현

 		
        int[,] nodes = new int[6, 6]
        {
            {0, 1, 0, 1, 0, 0 },
            {1, 0, 1, 1, 0, 0 },
            {0, 1, 0, 0, 0, 0 },
            {1, 1, 0, 0, 0, 0 },
            {0, 0, 0, 0, 0, 1 },
            {0, 0, 0, 0, 1, 0 },
        };

        bool[] visited = new bool[6];
        // 1)우선 now 부터 방문하고
        // 2)now와 연결된 정점들을 하나씩 확인해서, 아직 미발견 상태라면 방문한다.
        public void DFSByMatrix(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고.

            for(int next = 0; next < 6; next++)
            {
                // 연결되어 있는 정점이 아니면 패스.
                if(nodes[now, next] == 0)
                {
                    continue;
                }

                // 방문한 정점이면 패스.
                if(visited[next])
                {
                    continue;
                }

                DFSByMatrix(next);
            }
        }

구현시 주의할 점

- 정점이 모두 이어진 경우가 아니라면 dfs 탐색을 1회만으로 불가능 한 경우가 생긴다.

     
     	public void SearchAll()
        {
            visited = new bool[6];

            for(int now = 0; now < 6; now++)
            {
                if(visited[now] == false)
                {
                    DFSByMatrix(now);
                }
            }
        }

BFS

개념

- 너비 우선 탐색 (Breadth First Search)

- 연결된 정점 정보를 저장하고 저장된 순서대로 꺼내서 다음 탐색을 시작한다.

- 순서대로 정점 정보를 사용하기 때문에 queue가 사용된다.

- 주로 길찾기 알고리즘에 사용된다.

리스트를 이용한 구현

 class Graph
    {
        List<int>[] nodes = new List<int>[]
        {
            new List<int>() { 1, 3},
            new List<int>() { 0, 2, 3},
            new List<int>() { 1 },
            new List<int>() { 0, 1, 4},
            new List<int>() { 3, 5 },
            new List<int>() { 4 },
        };

        public void BFSByList(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 인접하지 않으면 패스.
                foreach (int next in nodes[now])
                {
                    // 이미 발견 했으면 스킵.
                    if (found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }
    }

행렬을 이용한 구현

 class Graph
    {
        int[,] nodes = new int[6, 6]
        {
            {0, 1, 0, 1, 0, 0 },
            {1, 0, 1, 1, 0, 0 },
            {0, 1, 0, 0, 0, 0 },
            {1, 1, 0, 0, 1, 0 },
            {0, 0, 0, 1, 0, 1 },
            {0, 0, 0, 0, 1, 0 },
        };

        public void BFSByMatrix(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while(q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                for(int next = 0; next < 6; next++)
                {
                    // 인접하지 않으면 패스.
                    if(nodes[now, next] == 0)
                    {
                        continue;
                    }

                    // 이미 발견 했으면 스킵.
                    if(found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }

        public void BFSByList(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 인접하지 않으면 패스.
                foreach (int next in adj2[now])
                {
                    // 이미 발견 했으면 스킵.
                    if (found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }
    }

DFS vs BFS

- dfs는 발견과 동시에 방문한다. 다른 루트에 의해서 발견되었다고 해도 내가 먼저 방문하면 장땡.

- bfs는 발견된 정보는 우선 queue에 저장하고 queue 정보를 토대로 순차적으로 방문한다.

logN

전제

- 이진트리의 탐색의 경우

- n : 전체 데이터 갯수

- x : 탐색 횟수(최악의 경우 특정 데이터를 찾기 위해 탐색해야 하는 횟수)

풀이

- The Binary Tree Algorithm

- The Sidewinder Algorithm

- Kruskal Algorithm

- Prim

정의

- 알고리즘의 효율을 표현하기 위한 기준

- 알고리즘의 시간 복잡도를 수치화 하기 위한 수단

계산 방법

- 수행 되는 연산(산술, 비교, 대입 등)의 갯수를 대략적으로 판단

- 가장 영향력이 큰 대표 항목만 남긴다 (ex n^2+1 -> n^2)

- 상수 무시 (ex 2n -> n)

읽는 법

EX) O(n^2)

- order of n 제곱

- 빅오 n 제곱

의의

- N^2

- NLogN (대부분의 정렬 알고리즘 NLogN의 시간 복잡도를 갖는다.)

- N

- LogN

- 1