글 읽기 - 시간초과 질문(비주얼에서는 안되는데..)

gounttt 6년 전 0

안녕하세요,

코드를 제출했더니 정답이라고도 나옵니다.

언어는 C++14를, visual studio 2017을 사용하였습니다.

신기한 것은 비주얼에서 돌리면 약 8초 뒤에 답이 나오더라구요..

혹시나 해서 다른 정답 코드를 돌려봐도

제 비주얼에서는 8초가량이 소모되고

여기에 제출하면 정답이라고 나옵니다.

혹시 이 문제 제한시간이 1초가 아닌가요??

아니면 제 비주얼이 이상한 걸까요..

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

int main()
{

	int start = 0;
	int input;
	for (int i = 0; i < 9; i++) {
		cin >> input;
		if (input == 0) input = 9;
		start = start * 10 + input;
	}
	map<int, int> m;
	queue<int> q;
	m[start] = 0;
	q.push(start);
	int next;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		string str_now = to_string(now);
		string str_next;
		int l9 = str_now.find('9');

		// 위
		if (l9 - 3 >= 0) {
			str_next = str_now;
			swap(str_next[l9], str_next[l9 - 3]);
			next = stoi(str_next);
			if (m.count(next) == 0) {
				m[next] = m[now] + 1;
				q.push(next);
			}
		}
		// 아래
		if (l9 + 3 < 9) {
			str_next = str_now;
			swap(str_next[l9], str_next[l9 + 3]);
			next = stoi(str_next);
			if (m.count(next) == 0) {
				m[next] = m[now] + 1;
				q.push(next);
			}
		}
		// 왼
		if (l9 > 0 && ((l9 - 1) / 3 == l9 / 3)) {
			str_next = str_now;
			swap(str_next[l9], str_next[l9 - 1]);
			next = stoi(str_next);
			if (m.count(next) == 0) {
				m[next] = m[now] + 1;
				q.push(next);
			}
		}
		// 오
		if (l9 < 8 && ((l9 + 1) / 3 == l9 / 3)) {
			str_next = str_now;
			swap(str_next[l9], str_next[l9 + 1]);
			next = stoi(str_next);
			if (m.count(next) == 0) {
				m[next] = m[now] + 1;
				q.push(next);
			}
		}

	}

	if (m.count(123456789) == 0) cout << -1 << endl;
	else cout << m[123456789] << endl;

	return 0;
}

djm03178 6년 전 1

혹시 디버깅 모드로 빌드하셨다면 디버깅을 위한 이런 저런 코드, 특히 STL에서 아주 많은 내용이 들어가서 매우 느려집니다.

jh05013 6년 전 1

8초라는 게 컴파일 시간을 포함하나요? 채점 시에는 컴파일 시간을 제외합니다.

gounttt 6년 전 0

실행시간만 8초가량 소모됩니다.

gounttt 6년 전 0

아.. 앞선 답변을 지금 봤습니다.

정말 release로 해보니 바로 출력이 되네요.

감사합니다.

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

문제

문제

출처

ICPC

시간초과 질문(비주얼에서는 안되는데..)

gounttt 6년 전 0

djm03178 6년 전 1

jh05013 6년 전 1

gounttt 6년 전 0

gounttt 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말