간단한 그래프에서 싸이클 체크, queue STL

used배열로 싸이클을 막을 수 있다. 

초기 출발지를 입력받는다면 첫 인덱스에 해당 값을 저장하고 시작

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

int used[4];
vector<vector<int>> map(4);

void dfs(int now)
{
    cout << now;
    for(int i=0; i<map[now].size(); i++)
    {
        
        int next = map[now][i];
        if(used[next] == 1) continue;
        used[next] = 1;
        dfs(next);
    }
}
int main()
{
    map[0] = {1, 2, 3};
    map[1] = {0};
    map[2] = {1, 3};
    map[3] = {1, 2};
    used[0] = 1;
    dfs(0);
    return 0;
}

 

가중치가 생겼을 때 vector, pair로 값 저장

#include <iostream>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> map(3);
int used[3], minNum = 1e9;

void dfs(int now, int sum)
{
    if(now == 2)
    {
        if(minNum > sum)
            minNum = sum;
        return;
    }
    for(int i=0; i<map[now].size(); i++)
    {
        pair<int, int> next = map[now][i];
        int cost = next.second;
        int go = next.first;
        if(used[go] == 1) continue;

        used[go] = 1;
        dfs(go, sum + cost);
        used[go] = 0;
    }
}
int main()
{
    map[0] = {{1, 5}, {2, 10}};
    map[1] = {{2, 2}};
    used[0] = 1;
    dfs(0, 0);
    cout << minNum;
    return 0;
}

구조체로 만들어서 pair 대신 넣어도 가능

가독성이 더 좋기도 하다.

#include <iostream>
#include <vector>
using namespace std;
struct Node{
    int a;
    int cost;
};
vector<vector<Node >> map(5);
int minNum = 1e9, used[5];

void dfs(int now, int sum)
{
    if(now == 4)
    {
        if(minNum > sum)
            minNum = sum;
        return;
    }
    for(int i=0; i<map[now].size(); i++)
    {
        Node next = map[now][i];
        if(used[next.a] == 1) continue;
        used[next.a] = 1;
        dfs(next.a, sum + next.cost);
        used[next.a] = 0;
    }
}
int main()
{
    map[0] = {{3, 2}, {2, 7}};
    map[1] = {{4, 1}};
    map[2] = {{1, 4}, {4, 6}};
    map[3] = {{2, 1}, {4, 30}};
    dfs(0, 0);
    cout << minNum;
    return 0;
}

 

모든 경로를 출력해야 하기에 used 초기화 및 path를 지움

#include <iostream>
#include <vector>
using namespace std;
struct Node{
    int a;
    int cost;
};
vector<vector<Node >> map(4);
int used[4];
char path[5];
void dfs(int level, int now, int sum)
{
    if(now == 3)
    {
        cout << path << "(" << sum << ")\n";
        return;
    }
    for(int i=0; i<map[now].size(); i++)
    {
        Node next = map[now][i];
        if(used[next.a] == 1) continue;
        used[next.a] = 1;
        path[level + 1] = next.a + 'A';
        dfs(level + 1, next.a, sum + next.cost);
        used[next.a]= 0;
        path[level + 1] = 0;
    }
}
int main()
{
    map[0] = {{1, 2}, {2, 6}, {3, 20}};
    map[1] = {{2, 3}, {3, 10}};
    map[2] = {{0, 1}, {3, 4}};
    used[0] = 1;
    path[0] = 'A';
    dfs(0, 0, 0);
    return 0;
}

 

level은 몇번 이동해야 하냐를 의미

 

 

queue STL 간단한 사용

#include <iostream>
#include <queue>
using namespace std;
struct Node
{
    int a, b;
};
int main()
{
    queue<Node> q;
    q.push({3, 5});
    q.push({4, 6});
    q.push({9, 3});
    q.push({10, 15});

    while(!q.empty()){
        cout << q.front().a << ' '<< q.front().b << '\n';
        q.pop();
    }
    return 0;
}