알고리즘/Baekjoon
[PS] 뱀과 사다리 게임 / C++ (백준 16928번)
dh_0e
2025. 4. 9. 22:43


BFS로 풀 수 있는 간단한 문제
greedy 방식이 왜 항상 최적의 값을 찾을 수 없는지 알려주기 좋은 문제같다.
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int d[101], vi[101];
queue<pair<int, int>> que;
int f(int cur, int c) {
for (int i = 1; i <= 6; i++) {
if (cur + i <= 100 && d[cur + i] == 0 && vi[cur + i] == 0) {
que.push(make_pair(cur + i, c + 1));
vi[cur + i] = 1;
}
else if(cur + i <= 100 && vi[d[cur+i]]==0){
que.push(make_pair(d[cur + i], c + 1));
vi[d[cur + i]] = 1;
}
}
return 0;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n + m; i++) {
int ori, des;
scanf("%d %d", &ori, &des);
d[ori] = des;
}
f(1, 0);
while (1) {
pair<int, int> pa = que.front();
que.pop();
if (pa.first == 100) {
printf("%d\n", pa.second);
break;
}
f(pa.first, pa.second);
}
return 0;
}