우리가 코딩할때 stack overflow나 블로그를 뒤져가면서 관련 코드를 찾고, 그대로 따라서 타이핑 해도 되지만, 바로 복사해서 쓰듯(ㅋㅋ), 객체의 생성때마다 매번 재생성 하고 관련 파라미터를 세팅해주는 것이 아니라, 이미 세팅된 애를 복사해서 사용할때 유용하다.
이미 세팅된 애를 복사해서 쓰기 때문에, 객체 생성과정이 매우 복잡 or 비용이 크다면 ( DB 에서 참조, File I/O 등 ) 해당 비용을 줄일 수 있다!
또, 팩토리 패턴처럼 별도의 creator를 만들지 않아도 되니 서브클래스 숫자가 줄어드는 장점도 있다.
여러분은 npc를 만들고 배치 시키는 기능을 지원하기 위한 사전 작업을 하기로 했다.
오픈월드 게임을 해본 분들은 아시겠지만, 메쉬만 다르고 똑같은 액션 똑같은 행동들을 하는 npc들이 즐비해있다. 실제 게임을 만들때 그러한 npc들을 여기저기 배치해둘 것이다. (안그럼 밋밋해보이고, 모든 npc를 개성있게 만들기에는 시간이 부족하며 가성비가 안나온다...)
clone 메소드를 override하여 각 종류의 npc 인스턴스를 만든뒤 대입 연산자를 통해 copy 한다.
(인스턴스의 copy를 shallow copy로 할지 deep copy로 할지는 요구사항에 따라 결정하여 구현한다.)
이제 npc들의 '원형'들을 만들어 store에 등록해두자!
(예제라 코드로 하지만, 실제 엔진이라면 툴 차원에서 지원할 것이다.)
NPCStore* store = NPCStore::This();
//1) speed가 빠른 행인 npc
NPC* npc = new WalkerNPC(200);
store->addNPCPrototype("Fast_NPC", npc);
//2) speed가 느린 행인 npc
npc = new WalkerNPC(10);
store->addNPCPrototype("Slow_NPC", npc);
//3) hp가 높은 고정 npc
npc = new FixedNPC(100000);
store->addNPCPrototype("High_Hp_NPC", npc);
//4) hp가 낮은 고정 npc
npc = new FixedNPC(20);
store->addNPCPrototype("Low_Hp_NPC", npc);
이처럼 store 같은 'manager'가 있으면 같은 class의 인스턴스라도 다른 state( WalkerNPC의 speed, FixedNPC의 hp)를
가지는 새로운 원형으로 등록시키는게 가능하다!
NPC* clonedNPC;
//1) speed가 느린 행인 npc
clonedNPC = store->getNPC("Slow_NPC");
clonedNPC->info();
//2) hp가 높은 고정 npc
clonedNPC = store->getNPC("High_Hp_NPC");
clonedNPC->info();
스토어로부터 새로운 npc 인스턴스를 얻었으니 배치할 수 있다!
이처럼 유용한 패턴이지만 역시 단점도 있다.
바로 clone() 메소드이다.
clone() 메소드를 반드시 구현해야 하는데, 다음과 같은 3가지 사항에서 clone() 메소드 구현이 어려울 수 있다.
1. 이미 존재하는 class를 prototype으로 만드려 할때 어려울 수 있다.
2. 언어적으로 '복사'를 지원하지 않는다.
3. 환형참조가 있는 object
또한, concrete class에서만 아주 특별하게 쓰는 field( member variable )가 있고, 이 field를 외부에서
참조해야 하는경우 결국 down cast가 발생한다.
(근데 이건 subclass를 은닉시키는 모든 상황에서 발생가능한 것이므로, 그러한 상황이 나오지 않게
디자인 패턴을 따로 공부하지는 않았고(학부때 관련 전공필수 과목이 없었다...), 현업에서 개발을 하다가
접하게 되어 조금씩 생각날때 정리를 해보려한다. 들어가기 전에 기억해야할 것은
책에 나온 패턴들을 곧이곧대로 사용하려 하면 안된다. "만능, 치트키" 같은 물건이 아니며, 맹목적으로
그러한 설계(상속, 연관등의 구조)를 따를 필요는 없다. 개념을 이해하고 유연하게 바꾸어 사용하자.
어차피 곧이 곧대로 적용할 수 있을 정도로 프로덕트 코드들이 단순하지 않다.
(늘 문제는 생각하지 못한곳에서 발생하는 프로그래밍의 오묘한 세계...)
개요
먼저는 Manager 계열의 Class 설계시 아주 빈번하게 사용되고 있는 "생성" 패턴인 Factory에대해 알아보려 한다.
그중에 가장 단순한 형태인 Simple Factory가 이번 주제인데, 사실 Simple Factory라고 부르지만
실제 "패턴"으로 치지는 않는 아주 단순한 구조이다.
왜 사용할까?
구상 클래스를 중심으로 작성되는 코드는 결합도가 높아서 나중에 수정사항들이 생기면 "빈번한" 수정을 가해야한다.
그래서 결합도를 줄여 유지보수성을 높이기 위해 자주 사용된다.
예를들어 다음과 같은 코드가 있다.
class Monster
{
public:
virtual void attack(void) = 0;
};
class MushroomMonster : public Monster
{
public:
virtual void attack(void)
{
std::cout << "Mushroom attacked!" << std::endl;
}
};
class SnailMonster : public Monster
{
public:
virtual void attack(void)
{
std::cout << "Snail attacked!" << std::endl;
}
};
int main(void)
{
Monster* monster1 = new MushroomMonster();
Monster* monster2 = new SnailMonster();
monster1->attack();
monster2->attack();
/*
...
*/
Monster* monster3 = new MushroomMonster();
Monster* monster4 = new SnailMonster();
monster1->attack();
monster2->attack();
return 0;
}
Monster class를 상속받는 버섯몬스터 클래스와 달팽이몬스터 클래스가 있고, 단순하게 new를 해서
부모 class의 pointer로 받아서 객체를 핸들링 하는 코드가 있다. 이때 기획이 바뀌어 몬스터들에게
"체력 게이지"라는 스펙을 넣게 되었다 하자. 모든 몬스터는 반드시 hp를 가져야 하므로,
setter 메소드가 아닌, constructor에 강제하는것이 좋으므로 다음과 같이 변경했다.
class MushroomMonster : public Monster
{
public:
MushroomMonster(int hp)
: _hp(hp)
{
}
virtual void attack(void)
{
std::cout << "Mushroom attacked!" << std::endl;
}
private:
int _hp;
};
class SnailMonster : public Monster
{
public:
SnailMonster(int hp)
: _hp(hp)
{
}
virtual void attack(void)
{
std::cout << "Snail attacked!" << std::endl;
}
private:
int _hp;
};
# _hp를 Monster에 추가해줄 수 있지만, 여기서는 순수 interface의 역할만 수행하도록하여 넣지 않음.
이렇게 되면 main 함수에서 다음과 같이 수정해줘야 한다.
int main(void)
{
Monster* monster1 = new MushroomMonster(10); // 수정
Monster* monster2 = new SnailMonster(20); // 수정
monster1->attack();
monster2->attack();
/*
...
*/
Monster* monster3 = new MushroomMonster(10); // 수정
Monster* monster4 = new SnailMonster(20); // 수정
monster1->attack();
monster2->attack();
return 0;
}
new operator로 구상클래스를 인스턴스화 하고 있는 모든 부분에 수정이 가해진다. 의존도가 높아(결합도가 큼)
유지보수가 어려워진다. 생성만 담당하는 간단한 Factory로 결합도를 줄일 수 있다.
class MonsterFactory
{
public:
enum class MonsterType : int
{
eMushroom = 0,
eSnail,
eCount
};
static Monster* createMonster(MonsterType type)
{
switch (type)
{
case MonsterType::eMushroom:
return new MushroomMonster(10);
case MonsterType::eSnail:
return new SnailMonster(20);
default:
// assertion
break;
}
}
};
int main(void)
{
Monster* monster1 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eMushroom);
Monster* monster2 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eSnail);
monster1->attack();
monster2->attack();
/*
...
*/
Monster* monster3 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eMushroom);
Monster* monster4 = MonsterFactory::createMonster(MonsterFactory::MonsterType::eSnail);
monster1->attack();
monster2->attack();
return 0;
}
Factory 클래스는 주로 생성만 담당한다 하지만, 게임쪽에서 Manager란 클래스는 생성&관리 까지하여,
Simple Factory의 기능 + 라이프사이클관리(= 소유권 관리) 까지 포함하는 경우가 더러 있다.
다익스트라와 달리 모든 노드 쌍에 관한 최단 거리를 구하는 '플로이드-워셜 알고리즘'이 있다.
(다익스트라를 각 노드에 대해 구하면 동일하게 모든 쌍에 관한 최단 거리를 구할 수 있다.)
동작
dist[i] = min( dist[i], dist[j] + wieght[j][i] )
(i노드까지의 최단거리) = (현재 i 노드까지의 최단거리), (이전 노드 j까지의 최단거리 + j 에서 i까지 거리)
두 값중 작은 값을 취하면 된다. 위 공식을 시작 노드로부터 점진적으로 진행시키면 된다.
BFS와 같이 queue를 이용하여 다음 노드로 진행 시키는데, 우선 순위 큐(힙)을 사용하면
업데이트 횟수가 줄어들어 더 빠르게 진행할 수 있다. (여기서도 우선 순위 큐로 설명한다.)
예시 그래프의 다익스트라 알고리즘의 진행
먼저 최단 거리를 저장한 배열을 선언하고 시작 노드(0번)에 거리(시작이므로 0)를 표시한 뒤,
나머지 노드에 INF(무한한값, 보통 -1로 둔다.)으로 채워 넣고, queue에 시작 노드를 넣는다.
1. queue에서 데이터를 꺼내어(0번) 연결된 모든 노드(1, 3번)의 거리를 계산하고 기록한 뒤,
기록된 거리값으로 queue에 삽입한다.
2. queue에서 데이터를 꺼내어(최소힙이므로 1번) 연결된 모드 노드(3번)의 거리를 계산하여 더 작으므로
업데이트 한다. 업데이트 되었으므로 다시 queue에 삽입한다.
3. queue에서 데이터를 꺼내고(3번) 연결된 모든 노드(2, 4번)의 거리 계산 후 기록한 뒤, queue에 삽입한다.
구현에 따라 다르지만, 현재 queue에 거리4로 먼저 넣은 3번 노드가 있지만 거리3으로 구한 것이 최단이므로,
무시된다. 최소힙으로 구현하는 이점이다.
4. queue에서 데이터를 꺼내어(2번) 연결된 모든 노드(1번)의 거리를 계산하지만 이미 1번에 더 작은 값이 있으므로,
무시된다. 또 데이터를 꺼내어(4번) 연결된 모든 노드(5번)에 대해 계산하여 갱신 시킨다. 그 후 queue에 넣는다.
5. queue에서 데이터를 꺼내어(5번) 연결된 모든 노드(4번)에 대해 계산하지만 이미 작은 값이 있어 무시된다.
queue에 더이상 데이터가 없으므로 알고리즘을 종료한다.
6. 시작 노드(0번)으로부터 각 노드까지의 최단 거리가 다 구해졌다.
코드
public class graph {
// 최소힙에 넣기 위해 정의한 (노드번호, 거리)쌍의 클래스
private class _pair implements Comparable<_pair> {
public int dst;
public int weight;
public _pair(int d, int w) {
this.dst = d;
this.weight = w;
}
// 비교를 위해 Override
@Override
public int compareTo(_pair target) {
return this.weight <= target.weight ? -1 : 1;
}
}
private ArrayList<_pair>[] adjList; // 인접 리스트
private PriorityQueue<_pair> queue; // 우선 순위 큐
private int[] shortestDist; // 최단 거리 배열
public graph(int n) {
adjList = new ArrayList[n];
shortestDist = new int[n];
Arrays.fill(shortestDist, -1);
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList();
}
queue = new PriorityQueue<>();
}
// 간선 추가
public void addEdge(int src, int dst, int w) {
this.adjList[src].add(new _pair(dst, w));
}
// 다익스트라
public void dijkstra(int start) {
// 시작 노드 삽입, 거리 행렬 기록
queue.offer(new _pair(start, 0));
shortestDist[start] = 0;
// 큐에 데이터가 없을 때까지
while (!queue.isEmpty()) {
_pair p = queue.poll();
for (_pair adj : adjList[p.dst]) {
int dist = adj.weight + p.weight;
// 계산된 거리가 기록되어있는 거리보다 작거나
// INF값( -1 )일 경우
if (dist < shortestDist[adj.dst] || shortestDist[adj.dst] == -1) {
shortestDist[adj.dst] = dist;
queue.offer(new _pair(adj.dst, dist));
}
}
}
}
// 최단 거리 배열 출력
public void printDist() {
for (int i : shortestDist) {
System.out.print(i + " ");
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
graph g = new graph(6);
g.addEdge(0, 1, 1);
g.addEdge(0, 3, 4);
g.addEdge(1, 3, 2);
g.addEdge(2, 1, 1);
g.addEdge(3, 2, 8);
g.addEdge(3, 4, 8);
g.addEdge(4, 2, 3);
g.addEdge(4, 5, 2);
g.addEdge(5, 4, 1);
g.dijkstra(0);
g.printDist();
}
}
저번 dfs코드를 재귀호출이 아닌 스택을 직접적으로 사용할 경우 중복 제거를 했어야 함에 반해,
bfs의 특성상 중복 제거를 하지 않아도 결과는 동일하다.
import java.util.*;
public class graph {
private int szVertex;
private ArrayList<Integer> adjList[];
private boolean visited[];
private Queue<Integer> queue; // for BFS
public graph(int v) {
szVertex = v;
visited = new boolean[szVertex]; // default false
adjList = new ArrayList[szVertex];
for (int i = 0; i < szVertex; i++) {
adjList[i] = new ArrayList();
}
queue = new LinkedList<Integer>();
}
public void addEdge(int from, int to) {
// 무방향 그래프이므로 반대의 경우도 추가
adjList[from].add(to);
adjList[to].add(from);
}
// 재귀 호출로 구현할 수 있지만 queue을 이용하여 구현하였다
public void BFS(int start) {
queue.add(start);
// queue가 비어질때까지 게속
while (queue.peek() != null) {
// queue에서 가장 오래전 삽입된 데이터를 꺼내어 방문 행렬에 표시하고 출력
int current = queue.poll();
// 미방문 정점의 경우
if (!visited[current]) {
visited[current] = true;
System.out.print(current + " ");
// 인접 리스트에서 미방문 정점의 경우 queue에 추가
for (int i : adjList[current])
if (!visited[i])
queue.add(i);
}
}
System.out.println();
}
// 첫노드가 주어지지 않을 경우 0번 부터
public void BFS() {
BFS(0);
}
}
public class bfs {
public static void main(String[] args) {
graph g = new graph(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.BFS(2);
}
}
