Boj 16928) 뱀과 사다리 게임

문제

백준 16928번

설명

처음에 이거 DP 인가 생각했는데 넓은 의미론 맞지만 점화식으로 푸는게 아니라 BFS 였음.

BFS 를 돌리면 되는데 각 발판에서 할 수 있는 일이 정해져 있으니 중복체크만 해주면 되었음.

시간 복잡도

O(n)

코드

struct LINE { 
	bool operator<(const LINE& in) { return from < in.from; }
	friend bool operator<(const LINE& a, const LINE& b) { return a.from < b.from; }
	int from, to;
};

LINE lines[61];
bool check[101];

int main()
{
	int n, m, tmp1, tmp2;
	cin >> n >> m;
	
	for (int i = 0; i < n+m; i++)
	{
		cin >> tmp1 >> tmp2;
		lines[i] = { tmp1, tmp2 };
	}
	
	sort(lines, lines + n + m);
	
	bool able[6];
	queue<int> works;
	works.push(1);
	int ans = 0;
	
	while (!works.empty())
	{
		int size = works.size();
		ans++;
		for (int i = 0; i < size; i++)
		{
			int cur = works.front();
			if (cur + 6 >= 100) {
				cout << ans;
				return 0;
			}
			works.pop();
			fill(able, able + 6, true);
	
			LINE* start = lower_bound(lines, lines + n + m, LINE{cur, 0 });
			LINE* end = upper_bound(lines, lines + n + m, LINE{cur+6, 0 });
			for (LINE* iter = start; iter != end; iter++)
			{
				able[iter->from - cur-1] = false;
				works.push(iter->to);
				check[iter->to] = true;
			}
			for (int i = 0; i < 6; i++)
				if (able[i] && !check[cur + i + 1]) 
				{
					works.push(cur + i + 1);
					check[cur + i + 1] = true;
				}
		}
	}
}