글 읽기 - 13913 (도대체 어디서 틀린건지 모르겠습니다

syleemk 4년 전 0

정상적으로 잘 실행이 되는데

자꾸 틀렸다 나오네요, 다른 분들 코드봐도 알고리즘은 동일한데 뭐가 문제인지 모르겠습니다.ㅜㅜ

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>

#define MAX 100001

using namespace std;

bool visited[MAX];
int dist[MAX];
int route[MAX]; // 부모노드 저장

void printRoute(int idx, int k) {
	stack<int> s;
	s.push(k);

	int now = route[k];
	while (route[now] != now) {
		s.push(now);
		now = route[now];
	}
	s.push(now);

	while (!s.empty()) {
		printf("%d ", s.top());
		s.pop();
	}
}

void bfs(int idx, int k) {
	visited[idx] = true;
	dist[idx] = 0;
	route[idx] = idx; // 부모 노드를 저장한다

	queue<int> q;
	q.push(idx);

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

		if (now == k) { // k에 도착하면 최단거리와 경로 출력
			cout << dist[now] << endl;
			printRoute(idx, k);
			break;
		}
		if (now - 1 >= 0 && visited[now - 1] == false) {
			visited[now - 1] = true;
			dist[now - 1] = dist[now] + 1;
			route[now - 1] = now;
			q.push(now - 1);
		}
		if (now + 1 < MAX && visited[now+1] == false) {
			visited[now + 1] = true;
			dist[now + 1] = dist[now] + 1;
			route[now + 1] = now;
			q.push(now + 1);
		}
		if (now * 2 < MAX && visited[now * 2] == false) {
			visited[now * 2] = true;
			dist[now * 2] = dist[now] + 1;
			route[now * 2] = now;
			q.push(now * 2);
		}
	}
}


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

	bfs(n, k);
}

mjkam 4년 전 1

처음부터 같은 위치에 있는 경우를 처리 하셔야 합니다.

반례

5 5

syleemk 4년 전 0

네 질문 적고나서 발견했어요!! 감사합니다!!

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

문제

문제

출처

ICPC

13913 (도대체 어디서 틀린건지 모르겠습니다

syleemk 4년 전 0

mjkam 4년 전 1

syleemk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말