글 읽기 - 메모리초과가 왜뜨는걸까요?

colorxxx 5년 전 0

이분탐색과 비슷하게 진행되므로 4자리수의 대한 탐색의 경우의수는 적을것으로 예상해서 bfs로 돌렸으며

테케답은 나옵니다. 그런데 메모리초과가납니다

매번 큐를 비워주고 tc를 다시 돌리는데도 메모리초과가 뜨더군요 ㅠ

어디가 문제인건가요인가요?

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

int T, A, B;
struct state{
	int num;
	string s;
};
queue <state> q; //매번 새로운 데이터로 해야함


int calc(int num, char type) {
	if (type =='D') {//D 2n mod 10000
		return 2 * num % 10000;
	}
	else if (type == 'S') {//S n-1
		if(num>=2)
		return num - 1;

		else if (num == 1) return 9999;
	}
	else if (type == 'L') {//L shift
		int fst = num / 1000;//제일 첫자리
		int tmp = num - fst * 1000;
		tmp *= 10;
		tmp += fst;
	}
	else if (type =='R') {//R shift
		int lst = num % 10; //제일 마지막자리
		int tmp = num / 10;
		tmp += lst * 1000;
	}
}
int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		
		cin >> A >> B; //4자리의 수, 고정
		
			int r1 = calc(A, 'D');
			int r2 = calc(A, 'S');
			int r3 = calc(A, 'L');
			int r4 = calc(A, 'R');

			q.push({ r1,"D" });//해당 변환한값, 변환횟수
			if (r1 == B) {
				cout << "D" << "\n"; continue;
			}
			q.push({ r2,"S" });//해당 변환한값, 변환횟수
			if (r2 == B) {
				cout << "S" << "\n"; continue;
			}
			q.push({ r3,"L" });//해당 변환한값, 변환횟수
			if (r3 == B) {
				cout << "L" << "\n"; continue;
			}
			q.push({ r4,"R" });//해당 변환한값, 변환횟수
			if (r4 == B) {
				cout << "R" << "\n"; continue;
			}
		


		while (!q.empty()) {
			int k = q.front().num; string c = q.front().s;
			//cout << k << " " << c << "\n";
			q.pop();
			if (k == B) {
				cout << c<<"\n";
				while (!q.empty()) q.pop();
				break;
			}

				int r1 = calc(k, 'D');
				int r2 = calc(k, 'S');
				int r3 = calc(k, 'L');
				int r4 = calc(k, 'R');

				q.push({ r1,c+"D" });//해당 변환한값, 변환횟수
				q.push({ r2,c+"S" });//해당 변환한값, 변환횟수
				q.push({ r3,c+"L" });//해당 변환한값, 변환횟수
				q.push({ r4,c+"R" });//해당 변환한값, 변환횟수
			
		}

	}
}


//bfs에서 초항연산..빼먹..아놔....
//만약 tc가 있는 bfs, 중간에 return 된다면 queueu를 main에 넣는게 좋다 초기화시킬때 편하게하기위해. queue의 size 늘어남
//연산 D를 통해서 이분탐색 비슷하게 탐색가능.. 2^10 ,bfs로 해도 가능하다.

djm03178 5년 전 4

모든 BFS의 기본입니다. 방문 체크를 반드시 해야 합니다. 안 그러면 중복된 원소가 큐에 삽입되고, 중복된 원소들이 큐에서 나와서 다시 중복된 원소를 배로 만들어내는 것이 반복되면 시간 / 공간복잡도 모두 지수형태를 가지게 됩니다.

colorxxx 5년 전 0

아... 감사합니다! 나올수있는 수 10000가지에 대해서 중복체크를 해줘야하는거군요

huozuyinshua 2년 전 0

djm03178 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리초과가 왜뜨는걸까요?

colorxxx 5년 전 0

djm03178 5년 전 4

colorxxx 5년 전 0

huozuyinshua 2년 전 0

djm03178 감사합니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말