글 읽기 - 이 코드는 다익스트라가 아닌가요? C++

tigerfrom2 1년 전 0

다익스트라는 시간이 24ms 정도 나온다고 하는데 저는 왜 0ms가 나오는지 알 수 있을까요?

부탁드립니다 고수님들 ㅠㅠ

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

#define MAX 100001

using namespace std;

int N, M;
bool visited[MAX] = { false, };
queue<int> Q;
int dis[MAX] = {1000,};

void BFS() {
	Q.push((N));
	dis[N] = 0;

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

		if (x * 2 < MAX && dis[x * 2] > dis[x]) {
			Q.push((x * 2));
			dis[x * 2] = dis[x];
		}

		if (x + 1 < MAX && dis[x + 1] > dis[x] + 1) {
			Q.push((x + 1));
			dis[x + 1] = dis[x] + 1;
		}

		if (x - 1 > -1 && dis[x - 1] > dis[x] + 1) {
			Q.push((x - 1));
			dis[x - 1] = dis[x] + 1;
		}
	}

	cout << dis[M];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < MAX; i++) {
		dis[i] = 10000000;
	}
	BFS();
}

shs0911 1년 전 0

이 코드는 다익스트라가 아니고 단순 BFS입니다.

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

문제

문제

출처

ICPC

이 코드는 다익스트라가 아닌가요? C++

tigerfrom2 1년 전 0

shs0911 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말