글 읽기 - c++ 뭐가 틀린걸까요?

1211ghkd 2년 전 0

dp로 해선 풀었는데 bfs로 하니까 되려 틀리네요.

대체 어떤 부분에서 잘못된건지 알 수 있을까요?

인터넷에서 찾은 코드랑 크게 다른거 같지도 않은데 자꾸 틀리다고 뜨네요.

#include <iostream>
#include <queue>
#include <vector>
#define _CRT_SECURE_NO_WARNINGS

#define MAX 100001
using namespace std;

int n, k;
int time[MAX];
bool visit[MAX];
int index[MAX];
queue<int> q;
vector<int> ans;

int main() {
	cin >> n >> k;

	q.push(n);

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		if (x == k) {
			int idx = x;

			while (idx != n) {
				ans.push_back(idx);
				idx = index[idx];
			}
			ans.push_back(n);

			break;
		}

		int x1 = x + 1;
		int x2 = x - 1;
		int x3 = 2 * x;

		if (0 <= x1 && x1 <= MAX && !visit[x1]) {
			q.push(x1);
			index[x1] = x;
			visit[x1] = true;
			time[x1] = time[x] + 1;
		}
		if (0 <= x2 && x2 <= MAX && !visit[x2]) {
			q.push(x2);
			index[x2] = x;
			visit[x2] = true;
			time[x2] = time[x] + 1;
		}
		if (0 <= x3 && x3 <= MAX && !visit[x3]) {
			q.push(x3);
			index[x3] = x;
			visit[x3] = true;
			time[x3] = time[x] + 1;
		}
	}

	cout << time[k] << "\n";

	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << " ";
	cout << "\n";

	return 0;
}

jcreate98 2년 전 0

배열 초기화 하셨나요?

1211ghkd 2년 전 0

무슨 배열 초기화를 말씀하시는건지 잘 모르겠네요...

jcreate98 2년 전 0

제 visual studio 환경에서는 쓰레기값이 들어가있는데

int time[MAX] = {0,};

bool visit[MAX] = {false,};

int index[MAX] = {0,};

집어 넣으면 값 제대로 나와요

1211ghkd 2년 전 0

전역 변수로 선언하면 처음 선언할때 자동으로 초기화되지 않나요?

그렇게 해도 채점시키니 똑같이 틀렸다고 뜨네요...

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

문제

문제

출처

ICPC

c++ 뭐가 틀린걸까요?

1211ghkd 2년 전 0

jcreate98 2년 전 0

1211ghkd 2년 전 0

jcreate98 2년 전 0

1211ghkd 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말