Equivalence class 코딩

1. 2차원 배열 (n x n) 

 O(\(n^2\)) >> O(nm)

compact한 입력이 아닐 때

 

#include <iostream>
#include <cstdio>

int n, m;

int MAP[1000][1000];

int Stack[10000];
int SP;

void Push(int x){
    Stack[SP++] = x;
    return;
}

int Pop(){
    return Stack[--SP];
}

int isEmpty(){
    return (SP == 0);
}

// x에서 y로 갈 수 있다고 표시
void setLink(int x, int y){
    MAP[x][y] = 1;
    return;
}

int LastForward[1000] = {0}; //노드마다 가지고 있는것
int NextFoward(int x){//node 번호 x
    LastForward[x]++;
    while(LastForward[x] <= n){
        if(MAP[x][LastForward[x]] == 1) return LastForward[x];
        else LastForward[x]++;
    }
    return -1;
}

int Visited[1000]; //각 노드를 방문 했는지 안했는지 표시하는 변수

int isMarked(int x){
    return Visited[x];
}

void Mark(int x){
    Visited[x] = 1;
}

int LastStart = 0; //지난번에 시작했던 곳
int NextStart(){
    LastStart++;
    while(LastStart <= n){
        if(isMarked(LastStart)== 0) return LastStart;
        else LastStart++;
    }
    return -1;
}



int main(int argc, const char * argv[]){
    int i, x, y; //x, y가 연결된 쌍을 읽기
    int cur, s;
    scanf("%d %d", &n, &m);
    for(i = 0; i < m; i++){
        scanf("%d %d", &x, &y); //쌍을 읽기
        setLink(x,y);
        setLink(y,x);
    }
    //stack을 이용한 dfs를 돌리면 됨
    while((cur = NextStart())!= -1){ //다음에 시작할 노드
        //첫번째 경우는 특수하게 처리해주기
        printf("%d", cur);
        Mark(cur); //current node는 도착했다고 mark
        while(1){
            if((s = NextFoward(cur)) != -1) {
                // current node에서 전진할 수 있을 때
                if(isMarked(s) == 0){
                    //아직 안 간 것
                    printf(" %d", s);
                    Mark(s); //다음 갈 곳을 마킹하기
                    Push(cur); //스택에 현재 노드를 push
                    cur = s; // 다음 갈 곳을 현재 위치로
                }
            }
            else {
                //후진 - 앞으로 갈 곳이 없음
                if(isEmpty() == 1) break; //스택이 비어있으면 break
                else{
                    cur = Pop();
                }
            }
        }
        printf("\n");
    }
    
    return 0;
}

 

2. counting을 통한 size가 다른 배열 버전 

O(n) >> O(n+m)

compact한 입력일 때 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m;

vector<int> MAP[1000];

int Stack[10000];
int SP;

void Push(int x){
    Stack[SP++] = x;
    return;
}

int Pop(){
    return Stack[--SP];
}

int isEmpty(){
    return (SP == 0);
}

// x에서 y로 갈 수 있다고 표시
void setLink(int x, int y){
    MAP[x].push_back(y);
    return;
}

int LastForward[1000] = {0}; //노드마다 가지고 있는것
int NextFoward(int x){//node 번호 x
    LastForward[x]++;
    if(LastForward[x] < MAP[x].size()) return MAP[x][LastForward[x]];
    else return -1;
}

int Visited[1000]; //각 노드를 방문 했는지 안했는지 표시하는 변수

int isMarked(int x){
    return Visited[x];
}

void Mark(int x){
    Visited[x] = 1;
}

int LastStart = 0; //지난번에 시작했던 곳
int NextStart(){
    LastStart++;
    while(LastStart <= n){
        if(isMarked(LastStart)== 0) return LastStart;
        else LastStart++;
    }
    return -1;
}



int main(int argc, const char * argv[]){
    int i, x, y; //x, y가 연결된 쌍을 읽기
    int cur, s;
    for(i = 0; i < 1000; i ++) LastForward[i] = -1;
    scanf("%d %d", &n, &m);
    for(i = 0; i < m; i++){
        scanf("%d %d", &x, &y); //쌍을 읽기
        setLink(x,y);
        setLink(y,x);
    }
    //stack을 이용한 dfs를 돌리면 됨
    while((cur = NextStart())!= -1){ //다음에 시작할 노드
        //첫번째 경우는 특수하게 처리해주기
        printf("%d", cur);
        Mark(cur); //current node는 도착했다고 mark
        while(1){
            if((s = NextFoward(cur)) != -1) {
                // current node에서 전진할 수 있을 때
                if(isMarked(s) == 0){
                    //아직 안 간 것
                    printf(" %d", s);
                    Mark(s); //다음 갈 곳을 마킹하기
                    Push(cur); //스택에 현재 노드를 push
                    cur = s; // 다음 갈 곳을 현재 위치로
                }
            }
            else {
                //후진 - 앞으로 갈 곳이 없음
                if(isEmpty() == 1) break; //스택이 비어있으면 break
                else{
                    cur = Pop();
                }
            }
        }
        printf("\n");
    }
    
    return 0;
}

 

 

 

3. Linked List 버전 -> O(n) 버전

#include <iostream>
#include <cstdio>

using namespace std;

int n, m;

class Node{
public:
    int a;
    Node *n;
};

class List{
    public :
    List();
    void insert(int x);
    int NextForward();
    Node *head;
    Node *LastForward;
};

List::List(){ head = NULL; LastForward = NULL;}
void List::insert(int x){
    Node *c;
    c = new Node;
    c->n = head;
    c->a = x;
    head = c;
}
int List :: NextForward(){
    if(head == NULL) return -1;
    if(LastForward == NULL) LastForward = head;
    else LastForward = LastForward->n;
    if(LastForward == NULL) return -1;
    else return LastForward->a;
    
}

List MAP[1000];

int Stack[10000];
int SP;

void Push(int x){
    Stack[SP++] = x;
    return;
}

int Pop(){
    return Stack[--SP];
}

int isEmpty(){
    return (SP == 0);
}

// x에서 y로 갈 수 있다고 표시
void setLink(int x, int y){
    MAP[x].insert(y);
    return;
}

int Visited[1000]; //각 노드를 방문 했는지 안했는지 표시하는 변수

int isMarked(int x){
    return Visited[x];
}

void Mark(int x){
    Visited[x] = 1;
}

int LastStart = 0; //지난번에 시작했던 곳
int NextStart(){
    LastStart++;
    while(LastStart <= n){
        if(isMarked(LastStart)== 0) return LastStart;
        else LastStart++;
    }
    return -1;
}



int main(int argc, const char * argv[]){
    int i, x, y; //x, y가 연결된 쌍을 읽기
    int cur, s;
    scanf("%d %d", &n, &m);
    for(i = 0; i < m; i++){
        scanf("%d %d", &x, &y); //쌍을 읽기
        setLink(x,y);
        setLink(y,x);
    }
    //stack을 이용한 dfs를 돌리면 됨
    while((cur = NextStart())!= -1){ //다음에 시작할 노드
        //첫번째 경우는 특수하게 처리해주기
        printf("%d", cur);
        Mark(cur); //current node는 도착했다고 mark
        while(1){
            if((s = MAP[cur].NextForward()) != -1) {
                // current node에서 전진할 수 있을 때
                if(isMarked(s) == 0){
                    //아직 안 간 것
                    printf(" %d", s);
                    Mark(s); //다음 갈 곳을 마킹하기
                    Push(cur); //스택에 현재 노드를 push
                    cur = s; // 다음 갈 곳을 현재 위치로
                }
            }
            else {
                //후진 - 앞으로 갈 곳이 없음
                if(isEmpty() == 1) break; //스택이 비어있으면 break
                else{
                    cur = Pop();
                }
            }
        }
        printf("\n");
    }
    
    return 0;
}