#include <iostream>

#define MAX_N 1000

using namespace std;

//adjacent array version

//A의 0 에 사이즈를 저장한 인접배열

int A[MAX_N+1][MAX_N+1];

int maxNode;

int D[MAX_N+1]; // distance

int U[MAX_N+1]; // selected vertex set

int UN=0;

void dijkstra(int s){

    U[s] = 1;

    cout << (char)(s+'a') <<" ";

    UN++;

    //0 에서 해당 정점까지의 거리를 초기값으로 입력한다.

    for(int i=0;i<=maxNode;i++){

        D[i] = A[s][i];

    }

    while(UN<=maxNode){

        //이미 선택되지 않은 정점중 가장 가까운 것을 찾는다.

        int min = 1000;

        int minIdx ;

        for (int i=0;i<=maxNode;i++){

            if( i!=s && !U[i] && min > D[i] && D[i]!=-1){

                minIdx = i;

                min = D[i];

            }

        }

        U[minIdx] = 1;

        UN++;

        cout << (char)(minIdx + 'a') <<" ";

        if(UN>maxNode){ break;} //it is really needed??

        for(int i=0;i<=maxNode;i++){

            if(A[minIdx][i]!=-1){

                //i 로 바로갈까 아니면 다른데 들러서 갈까?

                D[i] = (D[i] !=-1 && (D[i] < (D[minIdx] + A[minIdx][i])))?D[i]:(D[minIdx] + A[minIdx][i]);

            }

        }

    }

    //for(int i=0;i<=maxNode;i++){

    //    if(U[i]==0){

    //        cout << (char)(i + 'a') ;

    //    }

    //}

    cout << endl;

}

int main(){

    int T, test_case;

    int N;

    char src,dst;

    int weight;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        for(int i=0;i<=MAX_N; i++){

            for (int j=0;j<=MAX_N;j++){

                if(i==j)

   \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0                 A[i][j] = 0;

                else

                    A[i][j] =-1; // dijkstra 는 - 값을 다루지 않는다.

            }

        }

        cin >> N;

        cout << "Graph" <<endl;

        maxNode =0;

        for(int i=0;i<N;i++){

            cin >> src >> dst >> weight;

            A[src-'a'][dst-'a'] = weight;

            if (src-'a'> maxNode){

                maxNode = src-'a';

            }

            if (dst-'a'> maxNode){

                maxNode = dst -'a';

            }

        }

        for(int i=0;i<=maxNode;i++){

        for(int j=0;j<=maxNode;j++)

            cout << A[i][j] <<" ";

        cout << endl;

        }

        //Aijkstra

        dijkstra(0);

    }

    return 0;

}

//String quick sort

#include <iostream>

#include <stdio.h>

#define MAX_N 6

#define SWAP(a, b) do { a ^= b; b ^= a; a ^= b; } while ( 0 )

using namespace std;

inline int my_strlen(const char* str){int n=0;for(n=0;str[n]!='\0';n++);return n;}

int my_strcmp(const char* str1, const char* str2){

    if(str1[0]=='\0'|| str2[0]=='\0') return str2[0] - str1[0];

    int diff=0;

    for(int n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        diff = str2[n] - str1[n];

        if(diff!=0) return diff;

    }

    return diff;

}

int getLCP(const char* str1, const char* str2){

    int n;

    for(n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        if(str2[n] - str1[n]) break;

    }

    return n;

}

//adjacent list

int N;

char str[MAX_N + 1];

int suffixArray[MAX_N + 1];

int LCP[MAX_N + 1];

void quick_sort(int first, int last){

    int pivot, j, temp, i;

    if(first < last){

        pivot = first;

        i = first;

        j = last;

        while ( i < j){

            while (my_strcmp((char*)(str + suffixArray[i]),(char*)(str + suffixArray[pivot])) >= 0 && i<last) i++;

            while (my_strcmp((char*)(str + suffixArray[j]),(char*)(str + suffixArray[pivot])) < 0) j--;

            if(i<j){

                temp = suffixArray[i];

                suffixArray[i] = suffixArray[j];

                suffixArray[j] = temp;

            }

        }

        temp = suffixArray[pivot];

        suffixArray[pivot] = suffixArray[j];

        suffixArray[j] = temp;

        quick_sort(first,j-1);

        quick_sort(j+1,last);

    }

}

void calculateLCP(){

    LCP[0] = 0;

    for(int i=1;i<=N;i++){

        LCP[i] = getLCP((char*)(str+suffixArray[i - 1]), (char*)(str+suffixArray[i]));

    }

}

int main(){

    int T, test_case;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        //initialization

        //input

       \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0; cin >> str;

        cout << "["<<str<<"]" << endl;

        N = my_strlen(str);

        str[N] = '$';

        str[N+1] = '\0';

        //print suffix

        cout << "1. Suffix list" << endl;

        for(int i=0;i<=N;i++){

            suffixArray[i] = i;

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        quick_sort(0,N);

        cout << "2. Suffix array" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        calculateLCP();

        cout << "3. Suffix array and LCP" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " "<< LCP[i] <<" " << (char*)(str+suffixArray[i]) << endl;

        }

    }

    return 0;

}

Basic

- 상태공간 트리, Binary Search

Data Structure

- Tree 순회(Pre-order, In-order, Post-order)

String

- Suffix Array, LCP(Longest Common Prifix)

Graph

- BFS(Queue), DFS(Stack), Dijkstra, Fluid Warshall, KRUSKAL(Quick Sort)

Sort

- Quick Sort, Counting Sort

Tip.

- Map

- Bound check 는 별도 체크함수를 사용한다.

- 4방향을 배열에 넣고 상하좌우 넣고 반복문을 돌린다.

- Visit 여부는 맵자체에 값을 표기하여 갔던 곳을 다시 안가도록 처리한다. 돌아오면서 복원하게 되므로 다음번 시작할때는 문제가 발생하지 않는다. 물론, 변경, 복원 시점은 잘 생각해야한다.

- 2차원 배열의 행, 열을 탐색해야 할 때 transpose 하여 같은 방향으로 2 번 탐색을 수행하면 메모리는 낭비하지만 같은 루틴으로 작업을 하여 코딩 실수를 방지 할 수 있다.

//Data Structure

//Binary Tree Traversal Pre-order, In-order, Post-order

#include <iostream>

#include <stdio.h>

#define MAX_M 26

using namespace std;

//adjacent list

char tree[MAX_M][2];

int tree_len[MAX_M];

void preorder_traverse(int node){

cout <<" "<< (char)(node + 'A');

if(tree_len[node] > 0) preorder_traverse(tree[node][0]);

if(tree_len[node] > 1) preorder_traverse(tree[node][1]);

}

void inorder_traverse(int node){

if(tree_len[node] > 0) inorder_traverse(tree[node][0]);

cout <<" "<< (char)(node + 'A');

if(tree_len[node] > 1) inorder_traverse(tree[node][1]);

}

void postorder_traverse(int node){

if(tree_len[node] > 0) postorder_traverse(tree[node][0]);

if(tree_len[node] > 1) postorder_traverse(tree[node][1]);

cout <<" "<< (char)(node + 'A');

}

int main(){

int T, test_case;

int N;

freopen ( "sample_input.txt", "r", stdin );

cin >> T;

for(test_case = 1; test_case <= T; test_case++){

//initialization

for(int i=0;i<MAX_M;i++){

tree_len[i]=0;

}

//input

cin >> N;

for(int i=0;i<N;i++){

char cp,cc;

cin >> cp >> cc;

tree[cp-'A'][tree_len[cp-'A']] = cc - 'A';

tree_len[cp - 'A']++;

if(tree_len[cp - 'A']>2){

cout << "OOPS!!" << endl;

}

}

cout << "adjacent tree" << endl;

for(int i=0;i<MAX_M;i++){

if(tree_len[i]!=0){

cout << (char)(i+'A') << ":";

for(int j=0;j<tree_len[i];j++){

cout << " " << (char)(tree[i][j] + 'A');

}

cout << endl;

}

}

//pre-order traversal(binary tree only)

cout << "preorder_traverse : " << endl;

preorder_traverse(0);

cout << endl;

//in-order traversal(binary tree only)

cout << "inorder_traverse : " << endl;

inorder_traverse(0);

cout << endl;

//post-order traversal(binar tree only)

cout << "postorder_traverse : " << endl;

postorder_traverse(0);

cout << endl;

//DFS

//BSF

}

return 0;

}