글 읽기 - 시간초과 문제 - 어느부분이 잘못됬는지 잘 모르겠습니다.

kevin929292 5년 전 0

bfs와 visited를 체크해주었습니다. 어느부분에서 잘못되어서 시간초과가 나오는지 잘 모르겠습니다. 감사합니다.

시간초과가 나와서 아직 다른 테스트케이스에서 틀렸는지는 알수없습니다.

// https://www.acmicpc.net/problem/9019
/*
D, S, L, R을 사용하는 계산기

n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4

D: D save : 2n mod 10000
S: S save : n-1  / if(n==0) save : 9999
L: L 은 n의 각 자릿수를 왼편으로 회전 /  save : d2, d3, d4, d1
R: R 은 n의 각 자릿수를 오른편으로 회전 / save : d4, d1, d2, d3

A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램

//--------------------------------------------------------------------

bfs로 해야된다.
queue에 넣을때 문자열도 같이 가지고 가준다.

구조체 생성자를 만들고싶은데 쓰면 왜 고장나는지 모르겠다.
없어도 되는거지만 그냥 만들고 싶은데? ^오^
*/

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

struct node {
	int n;
	string str;
	node(int n, string str) : n(n), str(str) {}
};

bool flag[10005];

//------------------------------------------------------

int D(int n) {
	return (2 * n) % 10000;
}

int S(int n) {
	return (n + 9999) % 10000;
}

int L(int n) {
	return (n * 10) % 10000 + (n / 1000);
}

int R(int n) {
	return n / 10 + (n % 10) * 1000;
}

string claculator(int now, int ans) {
	queue<node> q;
	q.push(node(now, ""));


	while (!q.empty()) {
		now = q.front().n;
		string str = q.front().str;
		q.pop();

		if (flag[now] == true) continue;
		flag[now] = true;

		if (now == ans) return str;

		for (int i = 1; i <= 4; i++) {
			int next = 0;

			switch (i) {
			case 1: next = D(now); q.push({ next, str + "D" }); break;
			case 2: next = S(now); q.push({ next, str + "S" }); break;
			case 3: next = L(now); q.push({ next, str + "L" }); break;
			case 4: next = R(now); q.push({ next, str + "R" }); break;
			}
		}
	}
}

int main() {
	freopen("in.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		int A, B;
		cin >> A >> B;

		memset(flag, false, sizeof(flag));

		string ans = claculator(A, B);

		cout << ans << endl;
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 문제 - 어느부분이 잘못됬는지 잘 모르겠습니다.

kevin929292 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말