틀린점이나 이상한점  질문 등이 있을경우 아래 댓글로 알려주시면 감사하겠습니다.

타잔 Tarjan

 타잔 알고리즘은 SCC 를 찾는 알고리즘이다.

SCC란?  (Strong Connection Component) 강결합 컴포넌트 

간단하게 서로 연결되어있는 순한 노드끼리 묶어준다고 생각하면 쉽다.

크게 두개의 알고리즘이 있다고 볼수있는데

코사라주 알고리즘과 타잔 알고리즘이다.

이번엔 타잔 알고리즘을 설명하려 한다.

맨 아래에는 pc로 접속시(모바일은 사용불가) 코드를 눈으로 보며 생각과 맞는지 확인해볼수 있으니

본문을 읽어본뒤 테스트를 해보자.

알고리즘의 큰틀을 먼저 이해하면 구현자체는 쉽게 할수있다.

타잔알고리즘의 순서는

우선 함수 전 

count = 노드번호와 상관없이 노드를 처음탐색했을경우  탐색 번호를 의미한다.

lowset[]       = ( count  ) 를 넣어두는 배열 이며 비교할때 쓰인다.  그래프의 노드 사이즈와 같은 크기를 가지고 있다.

visit[]           = 노드 의 초기 (노드 카운터)를 넣어두는 배열 

 Tarjan 알고리즘 함수를 정의한다. 
    1. 노드 카운터를 증가시키고 현재 노드를 방문한 것으로 표시한다.
    2. 현재 노드를 스택에 푸시한다.
    3. 현재 노드의 이웃을 반복하며 방문한다
        a. 이웃이 아직 방문되지 않았다면, 재귀적으로 Tarjan 알고리즘을 호출한다.
        b. 이웃이 scc가 이미 되어있을경우 다시 돌아온다.

        c. 이웃의 노드 카운트와 lowset(내부의 count ) 값 을 비교후 작은값을  lowset  에 업데이트한다.
    4. 만약 방문할 노드가 없고 lowset[node] 값 이 현재 visit[node] 와 같다면, 강한 연결 요소(SCC) 발견 되었다.:
        a. SCC를 저장할 임시 벡터를 만든다.
        b. 현재 노드에 도달할 때까지 스택에서 노드를 팝하고, SCC 저장.
        c. SCC 벡터를 주요 SCC 벡터에 추가합니다.

예시를 들어

아래와 같은 그래프가 존재한다.

DFS로 하나씩 하나씩 들어가본다면

1->2->3->4->5

stack 1,2,3,4,5

5까지 도착한뒤 5에서 다시 연결되어있던 4로 돌아간다

위 이미지 처럼 이동한뒤 4->5 다시 5에 연결되어있던 4로 이동 한다.  

4의 경우 이미 방문했던 노드이기때문에   

두개의 node count 를 비교해준다

4노드가 들고있는 count  4 
5노드가 들고있는 count  5

가장 작은 노드인 4를 가져온다.

그렇다면

node   [1][2][3][4]   [5]    [6]

count  [1][2][3][4][5 > 4][x]

4번 확인뒤 5번은 방문할 노드가 없기때문에 4번노드로 돌아온다(DFS)

4->6번노드 방문시 5 번 노드와 같이

node   [1][2][3][4][5]   [6]

count  [1][2][3][4][4][6 > 4]

이후  더이상 갈수있는 노드가 없다.

들고있는 lowset[node] 값과 현재의 노드visit[node]의  값이 같은경우

stack 을 현재 노드까지  빼준다

stack [1,2,3,4,5,6] 

         [1][2][3][4][5][6]
 num = 4

stack[1,2,3] 

scc[0] = {6,5,4}

scc 묶음이 생겼다 

stack  {1,2,3}

4에서 돌아온뒤 노드 3번을 마저 탐색한다.

노드 1방문(이미 방문했던 노드)=> 더 작은노드 1 < 3 = 1을반환한다. 

num  = 1

작은값 갱신후 3번 노드 에서 더이상 갈수있는 노드가 없다. 

더작은 값을 을 num에 넣으며 현재 node 와 비교해주며 1번 노드까지 리턴되어 돌아온다

그럼 num  =1 

stack[1,2,3]

1 까지 stack을 빼준다.

CSS{{6,5,4},{3,2,1}}

코드로 보도록 하자.

코드는 두가지로  준비를 해두었다. low 값을 vector 로 저장하는 방법과

먼저 보이는 코드는 위 설명처럼 배열을 사용한다.

그 아래 코드는 가장 작은 값을 전달하는 식으로 만들어진 코드다.

두개의 큰 틀은 비슷하니 두개다 보면 이해가 쉬울수있다.

코드 1 

class TarjanSCC {
public:
    TarjanSCC(int nodes) : n(nodes), index(0), sccCount(0) {
        visit.resize(n, -1);
        lowset.resize(n, -1);
        onStack.resize(n, false);
    }

    void addEdge(int from, int to) {
        graph[from].push_back(to);
    }

    vector<vector<int>> findSCCs() {
        for (int i = 0; i < n; ++i) {
            if (visit[i] == -1) {
                tarjan(i);
            }
        }
        return sccs;
    }

private:
    int tarjan(int v) {
        visit[v] = index;
        lowset[v] = index;
        index++;
        stackNode.push(v);
        onStack[v] = true;

        for (int w : graph[v]) {
            if (visit[w] == -1) {
                lowset[v] = min(lowset[v], tarjan(w));
            } else if (onStack[w]) {
                lowset[v] = min(lowset[v], visit[w]);
            }
        }

        if (lowset[v] == visit[v]) {
            vector<int> scc;
            int w;
            do {
                w = stackNode.top();
                stackNode.pop();
                onStack[w] = false;
                scc.push_back(w);
            } while (w != v);
            sccs.push_back(scc);
            sccCount++;
        }
        return lowset[v];
    }

    int n;
    int index;
    int sccCount;
    unordered_map<int, vector<int>> graph;
    vector<int> visit;
    vector<int> lowset;
    vector<bool> onStack;
    stack<int> stackNode;
    vector<vector<int>> sccs;
};

코드 2

#include<algorithm>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;

stack<int> stackNode;
vector<bool> lowset;
vector<int> visit;
int nodecount = 0;
unordered_map<int, vector<int>> umap;
vector< vector<int>> scc;


int tajan(int index) {
	int num = 0;
	num = ++::nodecount;
	visit[index] = num;

	stackNode.push(index);
	for (int next : umap[index]) {
		if (visit[next] == -1) {
			num = min(tajan(next), num);
		}
		else if (lowset[next] == false) {
			num = min(visit[next], num);
		}
	}

	if (num == visit[index]) {
		vector<int> scc_temp;
		while (1) {
			int data = stackNode.top();
			stackNode.pop();
			lowset[data] = true;
			scc_temp.push_back(data);

			if (num == visit[data]) break;
		}
		sort(scc_temp.begin(), scc_temp.end());
		scc.push_back(scc_temp);
	}

	return num;
}

아래 시각화 도구로 확인해보자.

*그래프가 엉켜서 보기가 힘들다면*  클릭해서 노드 위치를 움직일수 있으니 보기 편하게 만든뒤 보면 보기 편하다

타잔 알고리즘 단계별 시각화 도구

C++ 의 std::function 을 이용하여 코드를 사용하기 쉽게 변경하기.

std::Function은 무엇인가

함수 포인터    =  반환값이 같은 타입이여야 하고 코드위치를 가르키기 때문에 메모리를 할당,회수가 불가하지만 빠르다.

std::Function  =  암시적 형변환이 가능하고

                           일반적인 함수포인터와 다르게 람다함수나 bind 또한 맴버함수에 대한 포인터도 사용가능하다

선언방법

int Func(int n){ cout<<n<<endl; };

std::function<void(int)> funcName1 = Func; //함수 대입
std::function<void(int)> funcName2 = [](int a) {}; // 람다함수
std::function<void(int)> funcName3 = std::bind(Func, 1); //std::bind

사용방법은 일반 함수와 같다

funcName1(10);

사용하는 이유

cpp로 player을 개발하던 도중 enum swich case 를 여러번 사용하는 경우를 보았다.

 메인업데이트 부분의 player 상태 처리와 렌더링부분의 player 상태처리 처럼  업데이트 상황을 나눠서 계산할때

state를 계속 추가해주었다.

업데이트 루프마다 플레이어의 상태들을 관리해 주는것은 player의 상황이 늘어났을경우 각종업데이트에서

swich를 써둬서 상황을 생성할때마다 swich문을 추가하는것과 커플링의 문제가보였다.

 이러한 문제는 코딩을 할때 일이 많아지고 코드의 길이가 길어져 비효율적이다.

 swich case를 state 패턴처럼 이용하며 함수들을 좀더 유동적으로 다루기위해

객체를 등록하여 사용이 필요했다.

위의 사진처럼 swich 문과 update를 하나의 루프에 묶어서 돌린다.

하나의 클래스에서  처음시작할때 원하는 위치에 함수를 받아서 저장 해둔뒤 실행하면 state에 따라 실행하게 고안하였다.

다른 오브젝트를 새로 생성하거나 제작할때 오브젝트의 init 함수에 특정 event를 걸어주게 만들면 알아서 돌아갈것이다.

장점

이런식으로 구조를 제작하면 새로운 상황을 추가할때 추가해주는 코드가 줄어들고

한쪽에서 코드를 지워도 문제없이 코드가 실행될것이다.

또한 하드코딩이 아니라 프로그램 내에서도 코드를 유동적으로 사용가능할것이다.

단점

유동적인 코드가 한번에 확인하기 어렵고, 필요한 순간 할당 제거를 할수있기에

나뉘어서 동작하는 함수들을 많이 추가하는 경우 서순이 꼬여서 생기는 찾기 어려운 오류가 생길수있다.

테스트 코드

//테스트 함수 추가를 위한 player 클래스
class Player
{
	
public:
	Player(int c) : b(c) { cout << a<<endl; };
	int b = 21;
	void playerMove( );
	void playerIdle( );
private:
	int a =10;

};

void Player::playerMove( )
{
	this->a+=this->b;
}

void Player::playerIdle( ) {
	cout << a<<endl;
}
//std::function 을 이차원 배열로 생성
class Deleg {
public:
	std::vector<std::function<void()>> Deleg;
};

//플레이어의 상태만큼 미리 event update의 크기를 만들어둘 예정
enum PlayerState 
{
	Move,
	Idel,
	Skill,
	StateCount
};



int main() {
	//Render update,LateUpdate,등 업데이트 순서
	const int UpdateRate= 2; 
	Player p = {Player(4)};
  	Player* _P = &p;
  
  Deleg StateDelg[PlayerState::StateCount][UpdateRate] = { { {} ,{} } ,{ {} ,{} } ,{ {}, {} } };
	StateDelg[0][0].Deleg.push_back([=]() {cout << endl; _P->playerMove(); cout << endl;  });
	StateDelg[0][1].Deleg.push_back([_P]() {_P->playerMove(); _P->playerIdle(); });


	StateDelg[1][0].Deleg.push_back([_P]() {_P->playerMove(); _P->playerIdle(); });
	StateDelg[1][1].Deleg.push_back([_P]() {_P->playerMove(); _P->playerIdle(); });


	StateDelg[2][0].Deleg.push_back([_P]() {_P->playerMove(); cout << "1Update End" << endl; });
	StateDelg[2][0].Deleg.push_back([_P]() {_P->playerMove(); cout << "1Update End" << endl; });
	StateDelg[2][0].Deleg.push_back([_P]() {_P->playerMove(); cout << "1Update End" << endl; });
	StateDelg[2][0].Deleg.push_back([_P]() {_P->playerMove(); cout << "1Update End" << endl; });
	StateDelg[2][0].Deleg.push_back([_P]() {_P->playerMove(); cout << "1Update End" << endl; });

	StateDelg[2][1].Deleg.push_back([_P]() {_P->playerMove(); _P->playerIdle(); });
  
  
  //전체 코드를 실행하지만 i나 j를 바꿔줌으로써 특정 state만 실행시켜줄수있다
	for (int i = 0; i < StateCount; i++)
		for (int j = 0; j < UpdateRate;j++) {
			for (int k = 0; k < StateDelg[i][j].Deleg.size(); k++) {
				(StateDelg[i][j].Deleg[k]());
			}

		}
  
 }

위 코드는 테스트 코드로써

1. 이차원 배열[플레이어 상태][ 업데이트 ] 를 만들어주었다.

    역으로 업데이트종류 마다 지정된 플레이어 상태에 맞는 함수를 실행시켜 주어도 좋다.

2. 함수(애니메이션 스크립트,스킬등)를 시작할때 원하는 [상태 또는 업데이트] 에 맞는 함수 리스트에 넣어준다.

3. 상황에 맞게 돌린다. 

이제 다른 함수들이 특정 state부분만 잠시 실행시키기 원해도 배열의 위치만 맞게 실행시켜주면 간단하게 사용가능하다.