자료구조와 알고리즘_1_Big-O 표기법 & 맵 만들기

 

[ ✔️Big-O 표기법 ]

 

📍Big-O 표기법 사용 이유 :

알고리즘의 효율 측정 기준으로 사용

 

📍Big-O 표기법 측정 순서 :

1. 대략적인 계산 

수행되는 연산의 개수를 대략적으로 판단

 

2. 대장만 남기기

영향력이 가장 큰 대표 항목만 남기고 삭제

상수 무시 (2N -> N)

 

ex)

 

📍그래프 : 

O(n) 보다 느린 시간 복잡도를 가진 알고리즘은 "실전성"이 없다고 생각하면 된다.

O(n log n) 시간 복잡도의 경우 "Sorting(정렬) 알고리즘"들이 이에 속하는데, 어느정도 사용할 순 있으나 자주 사용하지 않도록 한다.

Big-O 그래프 (refer : geeksforgeeks)

Big-O 그래프 (refer : https://medium.com)

 

---

[ ✔️미로 만들기 ]

 

📍기본 환경 설정 : 

25x25 타일 생성

 

해당 코드를 넣어 벽(WALL)과 빈공간(EMPTY)을 구분해준다. (red : wall , empty : green) 

void Board::GenerateMap()
{
    for (int32 y = 0; y < _size; ++y)
    {
        for (int32 x = 0; x < _size; ++x)
        {
            if (x == 0
                || x == _size - 1
                || y == 0
                || y == _size - 1)
                _tile[y][x] = TileType::WALL;
            else
                _tile[y][x] = TileType::EMPTY;
        }
    }
}

해당 코드를 해석하면 아래와 같이 2차원 배별에서 x,y 가 각각 "0(=첫)" 또는 "size-1(=마지막)" 인덱스 값을 가지는 부분은 "벽(wall)"로 설정하고 그 외 부분은 "텅빈(empty)" 구역으로 설정한다는 것을 알 수 있다.

결과

 

📍Binary Tree 미로 생성 알고리즘 :

참고서 : Mazes For Programers

기존의 맵 생성 함수에서 조건문을 아래와 같이 변경해준다.

void Board::GenerateMap()
{
    for (int32 y = 0; y < _size; ++y)
    {
        for (int32 x = 0; x < _size; ++x)
        {
            if (x % 2 == 0 || y % 2 == 0)
                _tile[y][x] = TileType::WALL;
            else
                _tile[y][x] = TileType::EMPTY;
        }
    }
}

위 코드를 보면 2차원 배열에서 x 또는 y의 인덱스가 짝수에 해당하는 부부은 tile의 설정을 empty → wall 로 변경한다.

결

 

이후, 초록색 공간을 기준으로 랜덤하게 벽을 뚫어주면 그럴싸한 미로가 생성된다.

---

코드 :

// Binary Tree 미로 생성 알고리즘
void Board::GenerateMap()
{
    for (int32 y = 0; y < _size; ++y)
    {
        for (int32 x = 0; x < _size; ++x)
        {
            if (x % 2 == 0 || y % 2 == 0)
                _tile[y][x] = TileType::WALL;
            else
                _tile[y][x] = TileType::EMPTY;
        }
    }

    // 랜덤으로 우측 혹은 아래로 길을 뚫는 작업
    for (int32 y = 0; y < _size; ++y)
    {
        for (int32 x = 0; x < _size; ++x)
        {
            // 벽
            if (x % 2 == 0 || y % 2 == 0)
                continue;
                
            // 출구
            if (y == _size - 2 && x == _size - 2)
                continue;

             // 출구의 좌측 벽 뚫기
            if (y == _size - 2)
            {
                _tile[y][x + 1] = TileType::EMPTY;
                continue;
            }

            // 출구의 위쪽 벽 뚫기
            if (x == _size - 2)
            {
                _tile[y + 1][x] = TileType::EMPTY;
                continue;
            }

            // 벽 랜덤으로 뚫기
            const int32 randValue = ::rand() % 2;
            if (randValue == 0)
            {
                _tile[y][x + 1] = TileType::EMPTY;	// 우측
            }
            else
            {
                _tile[y + 1][x] = TileType::EMPTY;	// 아래
            }
        }
    }
}

---

(노란색 : 플레이어 , 파란색 : 출구, 빨간색 : 벽, 초록색 : 빈공)

 

---

Next Note

자료구조와 알고리즘_2

 

 

================================

개인 공부 기록용 포스팅입니다.
댓글, 질문 환영해요~!

Refer : Inflearn_C++언리얼로 만드는...Part3
================================