갓겜만들기

그래프 기초

그래프란? 

현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한 것을 말한다.

그래프의 구성요소는 두 가지이며 다음과 같다.

 정점(Vertex) : 데이터를 표현한다.

간선(Edge) : 정점을 연결하는 데 사용한다.

오늘은 C++을 이용해서 그래프를 간단하게 구현하는 실습을 해보겠다.

우선 말로만 그래프를 표현하려고 해도 한계가 있으니 이미지를 확인해보자

보는 바와 같이 원이 정점이며 원 사이에 화살표가 간선이다.

각각의 원들이 다른 원을 가리키고 있는 것을 알 수 있다.

이제 이것을 구현해보자

우선 CreateGraph 함수를 만들고 메인에서 해당 함수를 호출해서 그래프를 구현하는 동작을 하게 할 것이다.

함수 내에 정점 Vertex를 만들고 Vertex 내부에는 다른 Vertex를 가리키는 간선을 만들었다.

하나의 Vertex에서 여러개의 간선을 가질 수 있으므로 벡터로 만들어서 관리하는 모습이다.

이제 Vertex를 선언하고 6개를 만들어주었다. 마찬가지로 여러 개의 Vertex를 벡터로 관리하는 모습이다.

그래프 개념 이미지를 참조하여 각각의 Vertex가 누구를 가리키고 있는지 간선에 저장하고 있다.

좀 더 자세히 말하면 0번 Vertex의 경우 1번과 3번 Vertex를 가리키고 있으므로 0번 Vertex 내부의

간선에 push_back을 이용해 1번과 3번 Vertex 주소를 넣고 있다.

주석의 질문을 해결하기 위한 코드이다. bool 값을 하나 만들고, 반복문에 0번 Vertex가 가지고 있는 간선을 가지고 와서

임시 변수인 edge에 넣어준 후 if문을 통해 조건에 맞는지 확인하고 있다.

조건에 맞다면 0번 Vertex에 3번 Vertex가 연결되어 있다는 뜻이므로 bool 값을 true로 바꿔준다.

이번에는 다른 방법을 통해 그래프를 구현해보도록 하겠다.

기존에는 Vertex안에 간선을 가지고 있는 형태였다면 이번에는 간선을 밖에서 관리하는 형태로 만들어보겠다.

이중 벡터, 즉 이중 배열을 만들고 6개의 정점을 만든다.

n번째 정점에 이중 배열을 이용해서 간선을 넣어주는 형태이다.

0번째 정점에 있는 간선을 꺼내와서 원하는 정점과 연결되어 있는지 확인하는 반복문이다.

각각의 구현 방법들이 상황에 따라 효율적인 상황이 다르기 때문에 잘 사용해야 한다.

이제 마지막으로 한 번 더 그래프를 다르게 구현해보도록 하겠다.

2-1 이미지처럼 연결된 간선을 따로 관리하지만 이번에는 6x6 크기의 2차원 배열을 통째로 만들고

기본 값을 false로 세팅한다. 그리고 연결된 간선만 true로 바꿔주면 된다. 

이것의 특징은 메모리 소모가 심하지만 빠른 접근이 가능하다. 그래서 간선이 많은 경우 효율적이다.

빠른 접근이 가능하기 때문에 특정 정점이 연결되어 있는지 확인하는 것이 매우 쉽다.

스택과 큐

stack은 LIFO(Last-In-First-Out, 후입 선출)의 특징을 가지고 있다.

대표적인 사용 예시로는 프로그래머들이 애용하는 Ctrl+Z가 있다. 

기본적으로 동적 배열이나 리스트의 동작 방식과 매우 유사하다. push, pop, front, empty, size 등의

기능들을 사용할 수 있다.

queue는 FIFO(First-In-First-Out, 선입선출)의 특징을 가지고 있다.

대표적으로 은행 대기열이나 다른 업종의 대기열, 게임내의 매치메이킹 등등에 사용된다.

스택보다 실전에서 자주 사용되는 것이 큐이다.

스택과 마찬가지로 push, pop, size, front, empty 등의 기능들을 사용할 수 있다.

[선형 구조 기초] 배열, 동적 배열, 연결 리스트

기초적인 선형 자료 구조를 복습해보자.

선형 구조는 알다시피 데이터를 순차적으로 나열한 상태를 말한다.

반대로 비선형 구조는 하나의 데이터 뒤에 다수의 자료가 올 수 있는 형태를 말한다.

선형 구조의 대표적인 기법

- 배열

- 연결 리스트

- 스택 / 큐

비선형 구조의 대표적인 기법

- 트리

- 그래프

배열

배열은 고정된 메모리 공간을 연속적으로 할당받아서 사용하는 선형 자료 구조이다.

고정된 공간이기 때문에 새로운 공간을 추가하거나 축소하는 등의 행동을 할 수가 없다.

그리고 무조건 연속된 공간에 할당되어야 한다는 특징이 있다.

동적 배열

배열을 개선한 것이 동적 배열이다.

일반 배열과 다르게 고정된 메모리 공간을 사용하지 않는다. 유동적으로 메모리 공간을 할당받아 사용할 수 있다.

일반 배열과 마찬가지로 할당받는 공간이 연속적이어야 한다. 연속적으로 할당받은 메모리 공간에 새로운 데이터를 

넣으려고 하는데 해당 공간이 부족하다면 다른 메모리 공간으로 이동해서 새롭게 할당을 받는 형식이다.

이러한 동적 배열은 메모리 공간이 부족하다면 계속 다른 공간으로 이동해야 하기 때문에 어찌 보면 비효율적이다.

하지만 다음과 같은 방법으로 해당 문제를 어느 정도 보완하고 있다. 바로 동적 배열 할당 정책이다.

특별한 게 있는 것은 아니고 실제로 사용할 공간보다 여유롭게(약 1.5~2배) 공간을 할당받는 방식이다.

매번 비효율적으로 메모리 공간을 이동하는 것이 비효율적이기 때문에 이러한 것을 최소화하기 위한 방법이다.

그럼 동적 배열은 단점이 없을까?

단점은 중간 삽입/삭제가 매우 비효율적이라는 것이다.

이 단점은 따로 대책이 없기 때문에 동적 배열을 사용하고 있다면 웬만하면 중간 삽입/삭제는 하지 않는 것을 권장한다.

연결 리스트

연결 리스트의 경우 연속되지 않은 메모리 할당 공간을 사용하는 특징이 있다.

각 공간들이 서로의 위치 정보를 가지고 있어서 이 위치 정보를 통해 다음 저장 공간으로 이동해서 데이터를

사용하는 방식이다. 그렇기 때문에 특정 공간의 데이터를 사용하고 싶을 때, 즉 중간 삽입/삭제에 이점이 있다.

데이터들이 연속된 공간에 할당되어 있는 것이 아니기 때문에 각 저장 공간에 있는 위치 정보만 수정하게 되면

중간에 삽입이나 삭제가 매우 간편하다. 

하지만 단점으로는 n번째 저장 공간을 빠르게 찾을 수 없다는 점이다. 다시 말해 임의 접근이 매우 비효율적이다.

그렇다면 여기서 모순점이 생긴다.

임의 접근이 좋지 않은데 중간 삽입/삭제는 왜 장점일까?

중간에 데이터를 삽입/삭제하기 위해서는 특정 지점의 위치를 알아야 할 텐데 그렇다면 임의 접근을 해야 한다는

소리 아닌가? 라고 생각할 수 있다. 맞는 말이긴 하지만 다음과 같은 방법으로 중간 삽입/삭제를 하게 된다.

특별한 방법은 아니고 특정 지점의 위치 정보를 따로 관리하는 것이다.

연결 리스트가 임의 접근이 비효율적이기 때문에 어느 공간으로 이동해야 할지 위치 정보를 따로 관리하게 되면

매우 효율적으로 특정 지점으로 이동할 수 있게 된다. 

이러한 관점에서 중간 삽입/삭제가 장점이라는 소리다.

오른손 법칙

자료구조와 알고리즘 공부를 시작하겠다.

Visual Studio의 콘솔을 이용해서 간단한 맵을 만들어놓고 다양한 알고리즘을 실습해보겠다.

콘솔 출력 창에 띄운 map이다. 

콘솔 관련 코드와 이중 반복문 등을 통해 제작한 것이고 자세한 건 생략하겠다.

우선 오른손 법칙이란 쉽게 설명하자면 미로에서 오른손을 벽에 대고 계속 이동한다고 생각하면 된다.

단순하고 무식한 방법이지만 웬만한 미로 등에 통하는 방법이기도 하다.

우선 1-1, 1-2 이미지와 같이 플레이어의 위치와 출구의 위치를 스택 메모리에 일시적으로 저장해놓는다.

저장해놓은 위치 정보를 토대로 플레이어가 출구에 도착할 때까지 반복하는 코드를 만들면 된다.

반복문을 이용해 플레이어가 출구에 도착할 때까지 반복하고 

오른쪽 길이 비어있는지 확인한 후 비어있다면 이동하는 코드이다.

_dir은 플레이어 클래스 내부에 선언된 플레이어가 바라보는 방향을 의미한다.

참고사항 이미지를 참고해서 코드를 해석하자면 

일단 오른쪽 방향을 보게 해야 하므로 _dir - 1을 해주고 음수가 있으면 안 되니까 DIR_COUNT를 더해준다.

그리고 DIR_COUNT를 나머지 연산을 해주게 되면 현재 바라보고 있던 방향에서 오른쪽으로 바라보게 된다.

이후에 오른쪽으로 이동할 수 있는지에 대한 함수를 만들고 현 위치에서 오른쪽으로 한 보 전진한 위치를 더하고 

해당 값을 매개값으로 넘겨준다. 그러면 만들어둔 CanGo 함수에서 해당 길이 비어있는지 확인해서 bool값을 뱉어준다.

바라보는 방향은 스택 메모리에 저장된 일시적인 값이기 때문에 실제 플레이어의 바라보는 방향을 바꾸기 위해

_dir += newDir을 실행해준다. 그리고 가야 하는 경로를 저장해주기 위한 vector 타입의 _path를 만들고

해당 벡터에 오른쪽으로 한 보 전진한  값을 넣어준다.

그외에 경우의 수도 다르지 않다.

오른쪽으로 갈 수 없다면 원래 바라보는 방향으로 일 보 전진하는 코드,

그것도 아니라면 왼쪽으로 방향을 회전하는 코드도 같은 원리를 이용하므로 생략하도록 하겠다.

이제 가야 할 경로를 벡터 _path가 저장하고 있는 상태이다. 

그럼 이제 _path를 이용해서 플레이어를 실질적으로 움직여야 한다.

움직이는 것은 Update에서 진행하면 된다.

_pathIndex는 경로를 기준으로 어디까지 이동했는지 추적하기 위한 값이다. 

해당 값이 _path 사이즈보다 크면 더 이상 갈 수 있는 경로가 없다는 뜻이기 때문에 리턴을 한다.

그리고 플레이어가 움직이는 것이 너무 빠르기 때문에 이것을 조절하기 위한 변수 _sumTick를 만들고

현재 시간 경과를 뜻하는 deltaTick의 값을 더해준다. 해당 값이 100(ms)을 넘었을 경우 

다시 _sumTick의 값을 0으로 초기화 해주고 실제 위치를 저장해두었던 경로로 순서대로 바꿔준다.

간략하게 주요 코드만 알아보았고 여기까지 문제 없이 진행하면 1-5 이미지처럼 플레이어가

출구로 오른손 법칙을 이용해서 이동하는 것을 확인할 수 있다.

해당 map을 만드는 코드와 그외 자세한 코드들은 자료구조 알고리즘 강의를 다시 보자.