STL queue, vector 연습

queue 익숙해지기

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

queue<int> arr;
int main()
{
    arr.push(3);
    arr.push(6);
    arr.push(1);
    arr.push(9);
    arr.push(7);
    arr.push(7);
    while(arr.size() > 1)
    {
        int temp = arr.front();
        arr.pop();
        temp *= arr.front();
        temp %= 11;
        arr.pop();
        arr.push(temp);
    }
    cout << arr.front();
    return 0;
}

 

queue, vector 사용하여 bfs로 트리 탐색하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> map(6);
int main()
{
    map[0] = {1, 3};
    map[1] = {2, 4};
    map[3] = {5};
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int now = q.front();
        cout << now;
        q.pop();
        for(int i=0; i<map[now].size(); i++)
        {
            int next = map[now][i];
            q.push(next);
            
        }
    }
    return 0;
}

 

level을 추가하여 운용해보기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node
{
    int n;
    int level;
};
int main()
{
    vector<vector<int>> map(6);
    map[0] = {1, 3};
    map[1] = {2, 4};
    map[3] = { 5};
    queue<Node> q;
    q.push({0, 0});
    while(!q.empty())
    {
        Node now = q.front();
        cout << now.n << ' ' << now.level << '\n';
        q.pop();
        for(int i=0; i<map[now.n].size(); i++)
        {
            int next = map[now.n][i];
            q.push({next, now.level + 1});
        }
    }
    return 0;
}

 

최단경로 출력

이러한 경우에 break로 탈출이 매우 불편하므로 함수로 빼서 작성한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node
{
    int n, level;
};
vector<vector<int >> map(7);
int used[7];
int main()
{
    map[0] = {1, 6};
    map[1] = {0, 2};
    map[2] = {3, 4, 5};
    map[3] = {5};
    map[4] = {5};
    map[5] = {2};
    map[6] = {2, 5};
    queue<Node> q;
    used[1] = 1;
    q.push({1, 0});
    while(!q.empty())
    {
        Node now = q.front();
        q.pop();
        for(int i=0; i<map[now.n].size(); i++)
        {
            int next = map[now.n][i];
            if(used[next] == 1) continue;
            used[next] = 1;
            q.push({next, now.level + 1});
            if(next == 5)
            {
                cout << now.level + 1;
                return 0;
            }
        }
    }
    
    return 0;
}

bfs는 모든 경로 탐색하는 것에 맞지않다. used배열을 전역으로 선언하여 사용할 수 없고 각 큐의 노드마다 used 배열을 가져야 하기 때문이다.

그렇게 된다면 메모리가 많이 쓰인다.