[23741] 야바위 게임

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> t;
vector<int> le;
int check[1001][1001];
void bfs(int src, int depth)
{
    queue<pair<int, int>> q;
    q.push({src, 1});
    check[src][1] = 1;
    int count = 1;
    while (!q.empty())
    {
        int temp = q.front().first;
        int tempcount = q.front().second;
        if (tempcount > depth)
            break;
        q.pop();
        vector<int> tt = t[temp];
        for (int i = 0; i < tt.size(); i++)
        {
            if (check[tt[i]][tempcount+1] ==1) continue;
            check[tt[i]][tempcount+1] = 1;
            q.push({tt[i], tempcount + 1});
            if (tempcount == depth)
            {
                le.push_back(tt[i]);
            }
        }
    }
    while (!q.empty())
    {
        q.pop();
    }
    sort(le.begin(), le.end());
    if (le.size() == 0)
    {
        cout << -1;
        return;
    }
    int temp = le[0];
    cout << temp << ' ';
    for (int i = 1; i < le.size(); i++)
    {
        if (temp == le[i])
            continue;
        cout << le[i] << ' ';
        temp = le[i];
    }
}

int main(void)
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    for (int i = 0; i < n; i++)
    {
        vector<int> s;
        t.push_back(s);
    }
    for (int i = 0; i < m; i++)
    {
        int src, des;
        cin >> src >> des;
        t[src].push_back(des);
        t[des].push_back(src);
    }
    bfs(x, y);
    return (0);
}

bfs 를 활용하는 문제이다. 처음에 시도했을때 메모리 초과가 났는데, queue 에 중복된 것이 넣어지면 메모리 초과가 난다.
따라서, check[i][j] 함수를 통해 i번째 정점 중 tempcount 가 j 일때 방문하는 것을 기록함으로써 queue 의 중복을 방지해준다.