[백준] 2963 무한 이진 트리 탐색💫

백준 2963 무한 이진 트리 탐색

• https://www.acmicpc.net/problem/2963

틀린 풀이

• 최악의 경우 BFS의 시간 복잡도 3^10000
  -> 시간 초과 & 메모리 초과

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

ull sum = 0;
string input;

void bfs() {

	//<node, index>
	queue<pair<ull, int>> q;
	q.push(make_pair(1, 0));

	while (!q.empty()) {
		pair<ull, int> cur = q.front();
		ull curnode = cur.first;
		int curindex = cur.second;
		q.pop();

		//bfs 횟수 줄이기 위해 * 만날 때 까지 while문 반복
		while (curindex < input.size()) {
			if (input[curindex] == 'L')
				curnode = curnode << 1;
			if (input[curindex] == 'P')
				curnode = curnode;
			if (input[curindex] == 'R')
				curnode = (curnode << 1) + 1;
			if (input[curindex] == '*')
				break;

			++curindex;
		}

		//base case
		if (curindex == input.size()) {
			sum += curnode;
			continue;
		}

		//bfs
		q.push(make_pair(curnode << 1, curindex + 1));
		q.push(make_pair(curnode, curindex + 1));
		q.push(make_pair((curnode << 1) + 1, curindex + 1));
	}

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> input;

	bfs();

	cout << sum;
	return 0;
}