BFS 알고리즘 보물섬 문제 (정올)


BFS는 항상 최단 경로만을 찾는다는 것을 명심하자.

목표지점까지 가는 루트가 많아도, 빙빙 둘러서

가는 경우가 없다. 왜냐하면 모든 루트가 큐에 저장되고

너비 우선탐색으로 진행되기 때문이다.

따라서 목표지점까지 중복된 곳을 방문하지 않으며,

목표지점까지 가는 길이 여러개인 경우

마지막에 비교를 통해 최저값을 찾아주기만 하면 된다.




BFS 보물섬 문제



01. 선언




02. 초기화 , 인큐, 디큐, 유효성 검사, 큐가 비었는지 검사




03. BFS 알고리즘 시작




04. 메인 함수




BFS 알고리즘은 DFS 알고리즘에 비해

이해하기도 쉬울 뿐더러 구현하기도 쉬운 것 같다.

어떠한 문제가 주어졌을 때 두 알고리즘 중에

어떤 것으로 풀어야 할 것인지 잘 캐치해야 할 것이다.



유니티 C# 자료구조 Dictionary (딕셔너리)



C#에는 많은 자료 구조가 있지만, 상황별로 가장

적절한 자료구조를 쓰는 것이 중요하다.

오늘은 게임 개발에서 유용하게 쓰일 수 있는

C# 자료구조 Dictionary에 대해 알아보고

이 자료구조가 왜 유용하지에 대해 알아보겠다.








먼저 여러 자료구조들의 추가, 검색, 삭제, 인덱스 접근에

대한 시간복잡도를 나타내는 표이다. 보시다시피 딕셔너리는

추가, 검색, 삭제 부분에서 상수시간의 시간복잡도를 보인다.

이것만 보아도 딕셔너리의 효율성을 짐작할 수 있다.




간단하게 딕셔너리의 사용법에 대해 알아보도록 하자.

먼저 Dictionary(딕셔너리)는 사용자가 원하는 대로 키를

설정할 수 있는 자료구조이다.  또한 이 키값으로 int뿐만아니라

문자열이나 다양한 변수형을 넣을 수 있다는 점이다.


 인터넷에 좋은 예제가 있어 실습겸 작성해보았다.




01. 아이템 클래스




02. Dictionary (딕셔너리) 선언 그리고 추가 , 검색




03. Dictionary(딕셔너리) 출력 , 삭제, 비우기




딕셔너리는 헤시 테이블과 상당히 유사하지만

헤시 테이블은 자료형에 대한 정의가 없다.

딕셔너리는 자료형을 명확하게 설정하기 때문에

속도면에서 딕셔너리가 좋은 성능을 보인다. (박싱 / 언박싱)

따라서 헤시 테이블 보다는 딕셔너리가 더욱 좋은 경우가 많다.




상황에 맞는 적절한 자료구조의 사용은

게임을 만드는 데 있어 성능향상을 가져오는

상당히 중요한 부분이기 때문에 많은 공부가

필요한 부분이 되겠다. 다음 포스팅은

헤시 테이블이 딕셔너리보다 느린 이유

박싱/언박싱에 대해 알아보도록 하겠다.


C++ UML 다이어그램 중

클래스 다이어그램에 대해 알아보자.




이때까지 C++을 공부하면서 UML 기호를

가끔 접했었는데, 내용 이해에 크게 문제가

되지 않아서 대충 넘어갔었다. 하지만 패턴을

공부하다보니 UML 다이어그램에 대해

꼭 알아야 할 것 같아서 포스팅을 진행한다.


배경지식이나 기본적인 이론에 대해서는 생략하겠다.

UML설계 방식은 제껴두고 클래스들간의

관계에 대해서만 짚고 넘어가겠다.




UML Class Diagram


1. 상속 (Inheritance)





02. 인터페이스 구현 (Interface Implimentation)




03. 연관 (Association)

한 클래스가 다른 클래스를 사용한다. 때문에 두 클래스 사이의

life time은 전혀 상관이 없다. 각각 독립적으로 생성되고

연결이 될 수도, 연결이 되지 않을 수도 있다.


ex)

class Car --------- class Person


class Car {

private:

Person person;


public:

setPerson(Person _p){

this.person = _p;

// setPerson 메소드를 호출해서 사용

}

}




04. 집합 (Aggregation)



Aggregation 관계로 표현되는 전체 객체의 생성 시기가

꼭 동일할 필요는 없다. 소멸시에도 Aggregatin 관계의

클래스들이 다른 객체에 의해 공유될 수도 있다.


ex)

class Car <>------------ class Engine


class Car{

private:

Engine engine;

public:

Car(Engine _e){

this.engine = _e;

// 생성자의 매개 변수로 들어온 놈이

// 꼭 Car과 같이 생성될 필요는 없으며

// 외부에서 생성된 Engine은 다른 객체에서도

// 사용되고 있을 수도 있다.

}

};




05. 구성 (Composition)


객체의 생성과 소멸 시기가 동일하다.

즉 Car 클래스 생성자 내에서 Engine 클래스를 생성한다.


ex)

class Car <<>>------------- class Engine


class Car{

private:

Engine engine;

public:

Car(...){

this.engine = new Engine( ... );

}

};




06. 의존 (Dependency)



객체의 생성과 소멸 시기와는 연관이 없다.


 ex)

Car - - - - - - - - - > Aircon


class Car{

...

public:

void Air( Aircon con){

con.turnOn();

// Aircon 클래스를 인자로 받아 메소드를 내부적으로 호출한다.

// Aircon 의 turnOn 의 정의가 바뀌면

// Car 에 영향을 주게 되므로 의존 관계에 있다고 말한다.

}

};




UML 다이어그램(클래스 다이어그램)에 대해

간략하게 알아보았다. 이 정도만 알고있어도

책에 나오는 UML기호는 어느정도 알아볼 수 있다.




간단한줄로만 알았던 UML 다이어그램이

상당히 복잡하고 덩치가 큰 분야라는 것을 알았다.

다음에 기회가 된다면 좀 더 자세히 알아보는 시간을 가지겠다.

+ Recent posts