백준 23741 야바위 게임
https://www.acmicpc.net/problem/23741
- 풀이
BFS를 사용하여 이동한 단계마다 queue에 push, 이동할 수 있는 다음 경로는 배열에 메모
메모리 초과가 나지 않도록 하기 위하여 queue를 비우면서 시행
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
// 23741 야바위 게임
int N, M, X, Y;
vi v[1111];
bool d[1111][1111];
queue<int> q;
void bfs(int x,int cnt) {
q.push(x);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i];
d[nx][cnt + 1] = true;
}
}
}
int main(void) {
fast;
memset(d, false, sizeof(d));
cin >> N >> M >> X >> Y;
for (int i = 0; i < M; ++i) {
int s, e; cin >> s >> e;
v[s].pb(e); v[e].pb(s);
}
if (!v[X].size()) {
cout << -1; return 0;
}
d[X][0] = true;
for (int i = 0; i < Y; ++i) {
for (int j = 1; j <= N; ++j) {
if (d[j][i]) bfs(j,i);
}
}
for (int i = 1; i <= N; ++i) {
if (d[i][Y]) cout << i << ' ';
}
}
- 메모리 초과가 나지 않도록 주의해야 하는 문제인 것 같습니다!
Author And Source
이 문제에 관하여(백준 23741 야바위 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@y-siro/BOJ-23741-야바위-게임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)