백준 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

알파벳 경로문제인데 풀이방법은 맞앗는데

MAP을 Queue담으면 메모리초과가 발생하고

그렇다고 map을 넣지않고 계산하면 시간초과가 발생했습니다.

그래서 이거저것 찾아보다가 bitset 을 이용하면 메모리초과를 회피할수 있었습니다.

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

void Prints(vector<vector<char>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
}
void Prints(vector<vector<bool>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
}
struct Data {
	int r;
	int c;
	bitset<26>save;
	int count = 0;
};

int gCount=0;
vector<vector<char>>maps;
void dfs( Data start,int c,int r) {
	int dirC[] = { 0,0,1,-1 };
	int dirR[] = { 1,-1,0,0 };

	if (gCount < start.count) {

		gCount = start.count;
		
	}

	for (int i = 0; i < 4; i++) {
		int tmpDirC = start.c + dirC[i];
		int tmpDirR = start.r + dirR[i];

		if (tmpDirC == -1 || tmpDirR == -1 || tmpDirC >= c || tmpDirR >= r) {
			continue;
		}
		if (start.save[maps[tmpDirR][tmpDirC]-'A'] == true) {
			continue;
		}

		Data tmpD;
		tmpD.c = tmpDirC;
		tmpD.r = tmpDirR;
		tmpD.save = start.save;
		tmpD.save[maps[tmpDirR][tmpDirC]-'A'] = true;
		tmpD.count = start.count + 1;
		
		dfs(tmpD,c,r);

	}

}

int main() {
	int r;
	int c;

	cin >> r;
	cin >> c;
	vector<bool>tmpbCheck(c, false);
	vector<vector<bool>>bCheck(r, tmpbCheck);
	string tmpstr;
	

	for (int i = 0; i < r; i++) {
		cin >> tmpstr;
		vector<char>tmpMaps;
		for (int j = 0; j < c; j++) {
			tmpMaps.push_back(tmpstr[j]);
		}
		maps.push_back(tmpMaps);
	}

	Data d;
	d.c = 0;
	d.r = 0;
	d.count = 1;
	
	d.save[maps[0][0]-'A']=true;
	dfs( d, c, r);
	cout << gCount;

	return 0;
}

아래는 챗 gpt 답변