[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 의 중복을 방지해준다.
Author And Source
이 문제에 관하여([23741] 야바위 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@worldicate/23741-야바위-게임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)