[백준 15558] 점프 게임 (C++)

문제 링크: https://www.acmicpc.net/problem/15558

15558번: 점프 게임

1. 주의할 점

- 현 자리에서 이동을 했을 때 N-1칸보다 높게 갈 수 있다면 끝난다

- 사라질 예정인 줄로 가지 않도록 한다

 

2. 구현

- BFS를 통해 구현하며, 현 위치를 Check[0][idx]라고 하면, Check[0][idx-1], Check[0][idx+1], Check[1][idx+jmp]로 갈 수 있다.

- 단, 뒤로 이동하는 경우는 사라질 칸(Banned)으로 이동하지 않도록 한다

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct info {
	int idx, ladder;		//현재 몇번째 칸인지(0~num-1), 어떤 줄인지(0~1)
};
info tmp;
bool check[2][100000] = { false, };

int main() {
	string str[2];
	int num, jmp;
	cin >> num >> jmp;
	cin >> str[0] >> str[1];
	queue<info> q;
	tmp.idx = 0;
	tmp.ladder = 0;
	q.push(tmp);
	check[0][0] = true;
	int result = 0;
	int banned = -1;		//사라진 가장 위 층수
	while (!q.empty()) {
		int len = q.size();
		for (int k = 0; k < len; k++) {
			int cidx = q.front().idx;
			int cl = q.front().ladder;
			q.pop();
			int limit = banned + 1;
			if (cidx - 1 > limit && !check[cl][cidx-1] && str[cl][cidx-1]=='1') {		//밑으로 가능한 경우
				check[cl][cidx - 1] = true;
				tmp.idx = cidx - 1;
				tmp.ladder = cl;
				q.push(tmp);
			}
			if (cidx + 1 > limit && !check[cl][cidx + 1] && str[cl][cidx + 1] == '1') {
				check[cl][cidx + 1] = true;
				tmp.idx = cidx + 1;
				tmp.ladder = cl;
				q.push(tmp);
			}
			if (cidx + jmp >= num) {
				result = 1;
				break;
			}
			if (cidx + jmp < num && !check[1 - cl][cidx + jmp] && str[1 - cl][cidx + jmp] == '1') {
				check[1 - cl][cidx + jmp] = true;
				tmp.idx = cidx + jmp;
				tmp.ladder = 1 - cl;
				q.push(tmp);

			}
		}
		banned += 1;
		if (result) break;
	}
	cout << result;
	system("pause");
	return 0;
}