C++/ DFS 완전탐색 -이중배열, STL vector pair

 

인프런 dfs 강의 58번~68번까지 들은 후에 정리하는 글

 

"완전 탐색"을 가능하게 하는 dfs 함수로 경로탐색, 미로탐색, 최소비용 문제를 풀어보았다.

문제를 풀면서 무방향 그래프, 방향 그래프 모두 이차원 배열로 구현해 본 후에

vector pair 자료구조를 이용해서 더 효율성 있는 코드 작성법을 배웠다.

 

1. void DFS(int vertex)

문제를 풀면서 쓰인 dfs 함수의 구조는 거의 동일했다.

if 문을 이용해 재귀함수를 빠져나올 조건을 걸고, else 문에서 다음 경로로 가는 코드를 짠다.

 

void dfs(int v){
    int i;
    if(v==n){
        cnt++;
    }
    else{
        for(i=1;i<=n;i++){
            if(map[v][i]==1 && ch[i]==0){
                ch[i]=1;
                dfs(i);
                ch[i]=0;
            }
        }
    }
}

문제가 동일하게 vertex 1에서 n까지 가는 경로 탐색 문제였기 때문에 return 조건은 모두

if(v==n) 이였다.

 

n에 도달하지 않았을 경우 탐색을 계속하게 되는데,

여기서 ch 배열은 경로를 기록하기 위한 배열이므로 기준 vertex v의 인접 vertex i에 방문한 기록이없다면

방문 기록 (ch[i]=1)을 해준 후 dfs 탐색을 계속한다. 다음 줄에서는 다시 방문 기록을 지워줘야함.

 

스택을 그려놓고 재귀함수를 따라가면 이해가 쉽다!

 

2. 자료구조 - 이차원 배열

무방향이든 방향 그래프든 가중치든 가장 간단하게 생각해낼 수 있는 자료구조가 이차원 배열 일것이다.

int map[30][30] 으로 잡아놓고 풀었을 때 우선 제일 큰 단점은 이중루프를 이용해 값을 넣어야하는 것일 것이다.

또한 한 vertex에 연결된 vertex의 개수에 상관 없이 정해진 배열 공간을 생성하므로 메모리 낭비가 크다

 

3. 자료구조 - vector을 이용한 인접 리스트

 

vector<int> map[30]

 

이렇게 벡터를 정의한다는 것은 크기가 30인 벡터 하나를 만드는 것이 아니다 !! (나중에 헷갈리지 말기)

가변크기의 map이라는 벡터를 30개 생성하는 것이다

이런 인접 리스트를 이용하면 접근 시간도 절약하고 메모리 절약도 절약이 가능하다.

 

#include <stdio.h>

using namespace std;
int ch[30], cnt=0, n;
vector<int> map[30];

void dfs(int v){
    int i;
    if(v==n){
        return;
    }
    else{
        for(i=0;i<map[v].size();i++){
            if(ch[map[v][i]==0]{
                ch[map[v][i]]=1;
                dfs(map[v][i]);
                ch[map[v][i]]=0;
            }
        }
    }
}
int main(){
    int m, i, j, a, b;
    scanf("%d %d", &n, &m);
    for(i=1;i<=m;i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
    }
    ch[1]=1;
    dfs(1);
    printf("%d",&cnt);
    return 0;

}

dfs 함수 내부에서 이중배열을 사용했을 때는 for loop 구간이 1에서 n 이였다면

인접 리스트를 사용했을 때는 0에서 map[v].size() 즉 v에 연결된 간선 개수 만큼의 구간만 돌면 되는 것이다.

위의 코드는 가중치가 없는 버전. 가중치 그래프는 단순히 해당 리스트에 값을 넣어주면 되는 것~!

 

3. 자료구조 - STL pair 

This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second.   -출처 cplusplus

pair 자료구조는 튜플에서 파생된 자료구조로 first와 second 두 개의 원소로 이루어진다.

벡터 내부에 pair를 생성하기 위해서는

vector<pair<int,int> > map[n]

이렇게 정의를 해주면 된다.



pair

스택에 저장된 pair 자료의 도식.

pair 자료형에 새로운 데이터를 삽입하려면

 

map = make_pair(변수1, 변수2)

혹은

map = {3,5}

 

vector에 집어 넣고싶다면?

    vector<pair<int,int> > graph[3];
    graph[1].push_back({3,5});
    graph[1].push_back({4,7});
    graph[2].push_back(make_pair(7,7));

이런식이다,, make_pair를 사용하는게 기억하기 쉽고 쓰기 간결하다고 생각한다.

 

#include <stdio.h>
#include <vector>

using namespace std;

int ch[30],n,cost=2147000000;
vector<pair<int,int> > map[n];

void dfs(int v, int sum){
    int i;
    if(v==n){
        if(sum<cost) cost = sum;
    }
    else{
        for(i=0;i<=map[v].size();i++){
            if(ch[map[v][i].first]==0){
                ch[]=1;
                dfs(map[v][i].first,sum+map[v][i].second);
                ch[map[v][i].first]=0;
            }
        } 
    }
}
int main(){
    //pair<int,int> p;
    //p.first p.second
    //p=make_pair(a,b)
    int m, i, a, b, c;
    scanf("%d %d",&n, &m);
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&c);
        map[a] = make_pair(b,c);
    }
    ch[1]=1;
    dfs(1,0);

}

 

pair를 이용한 가중치 방향그래프 dfs 코드이다

 

아자아자 홧팅이닷