[PS] 뱀과 사다리 게임 / C++ (백준 16928번)

 

 

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;
}