글 읽기 - 다익스트라 말고 다르게 풀었습니다..

alohajihwan 7년 전 0

다익스트라 말고 각각의 indegree를 저장하고 indegree[i]값이 0일때 큐에 넣어 경로를 계산해 주었는데 왜 틀렸는지 궁금합니다...ㅠㅠ

이 코드는 dp문제처럼 모든 경우를 다 고려했다고 생각했는데 제 생각이 잘못된 것인지 알려주세요ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>
using namespace std;

int n,m;
vector<pair<int,int> >adj[1001];
vector<int>path;
int indegree[1001];
int dp[1001];
int parent[1001];
void solve()
{
	queue<int>q;
	q.push(1);

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

		for(int i=0;i<adj[here].size();i++){
			int next = adj[here][i].first;
			int cost = adj[here][i].second;
			if(dp[next] < dp[here]+cost){
				dp[next] = dp[here]+cost;
				parent[next] = here;
			}
			indegree[next]--;
			if(indegree[next] == 0){
				q.push(next);
			}
		}
	}
}
void findPath()
{
	int here = 1;
	while(true){
		path.push_back(here);
		here = parent[here];
		if(here == 1){
			path.push_back(1);
			break;
		}
	}
	reverse(path.begin(),path.end());
	for(int i=0;i<path.size();i++)
		cout << path[i] << " ";
	cout << endl;
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b,c));
		indegree[b]++;
	}
	if(n == 1){
		cout << '0' << endl << '1' << endl;
		return 0;
	}
	parent[1] =1;
	solve();
	cout << dp[1] << endl;
	findPath();
}

	

wowoto9772 7년 전 1

일단, 확실하지는 않지만

위상정렬은 cycle이 있으면 사용이 안된다고 알고 있어요.

koosaga 7년 전 1

디버깅은 못해드리겠지만 문제조건에 사이클이 없다고 나와서 풀이는 맞는거같아요

alohajihwan 7년 전 2

위상정렬과 다익스트라 모두 맞네요!

제가 놓쳤던 부분은 만약 중간에 1로 가는 과정이 있는 경우 제 알고리즘이 그 과정에서 끝나 버립니다. 더 좋은 길이 다음 과정에 있을지라도 확인이 안됩니다..

따라서 here == 1이 나오면 일단 pop 해줘서 다음 path를 검사할 수 있는 기회를 주는 것이 이 문제를 고치는 핵심이었습니다.

도움주신 wowoto9772, koosaga님들께 감사드립니다..ㅠㅠ

ainch96 7년 전 0

혹시 왜 이게 다익스트라 인지 알려주실수 있나요??? 이해가 안되서... ㅠㅠㅠ

koosaga 7년 전 2

헉 최장경로군요. 다익스트라로 풀 수 없습니다. 반례 데이터가 복잡하긴 하지만 TLE를 낼 수 있습니다

alohajihwan 7년 전 0

다익스트라의 코드를 이용했습니다. 처음에 모두 음수간선으로 바꾼다음에 벨만포드 알고리즘으로 최소값을 찾으면 답을 구할 수 있다고 생각했습니다.

저도 최단경로가 아니라서 다익스트라를 배제하고 위상정렬을 이용해서 풀었는데 다익스트라 코드를 이용해도 풀리네요ㅠㅠ..

자세한 알고리즘은 잘 모르겠습니다..ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>
#include<functional>

#define INF 9876543321
using namespace std;
int n,m;

vector<pair<int,int> >adj[1001];
vector<int>path;
int indegree[1001];

int parent[1001];
vector<int> dist;
void solve()
{
	dist[1] = 0;
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,1));
	bool ok = true;
	while(!q.empty()){
		int cost = q.top().first;
		int here = q.top().second;
		q.pop();
		if(here == 1){
			if(!ok) continue;
			ok = false;
		}
		//if(dist[here] < cost) continue;
		for(int i=0;i<adj[here].size();i++){
			int there = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;
			if(dist[there] < nextDist){
				dist[there] = nextDist;
				parent[there] = here;
				q.push(make_pair(nextDist,there));
			}
		}
	}
}
void findPath()
{
	int here = 1;
	while(true){
		path.push_back(here);
		here = parent[here];
		if(here == 1){
			path.push_back(1);
			break;
		}
	}
	reverse(path.begin(),path.end());
	for(int i=0;i<path.size();i++)
		cout << path[i] << " ";
	cout << endl;
}
int main()
{
	cin >> n >> m;
	dist.assign(n+1,0);
	for(int i=0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b,c));
	}
	if(n == 1){
		cout << '0' << endl << '1' << endl;
		return 0;
	}
	
	solve();
	cout << dist[1] << endl;
	findPath();
}

	

alohajihwan 7년 전 0

다익스트라가 최장 경로가 안되는 이유가 사이클이 생기면 무한대의 값으로 돌기때문입니다.

근데 문제에서 사이클이 없다는 조건이 있기 때문에 그냥 트리에서 다익스트라 돌리듯이 생각하시면 이해하시기 쉬울거라 생각합니다!

따라서 다익스트라 코드를 이용해 풀어도 풀리는 거구요..

koosaga 7년 전 2

다익스트라는 음수 간선이 하나라도 존재하면 종료를 보장할 수 없습니다. 이는 사이클의 존재 여부와 관련이 없습니다.

alohajihwan 7년 전 0

음수 간선이 존재하지 않는 문제 입니다. 처음에 모든 간선을 음수간선으로 만들어 주고 다익스트라로 구현 할려고 했는데

다익스트라 증명에서 모든 간선이 양수이어야 한다는 조건 때문에 그 방식으로 안풀었습니다.

결론은 음수 간선은 존재하지 않고, 사이클이 존재하지 않는 다는 문제 조건때문에

위상 정렬을 사용할 수 있고 더 나아가서 다익스트라를 돌려도 최장길이 간선을 구할수 있습니다.

koosaga 7년 전 2

"다익스트라는 음수 간선이 하나라도 존재하면 종료를 보장할 수 없습니다. 이는 사이클의 존재 여부와 관련이 없습니다."

이 명제는

"max-heap으로 구현한 최장 경로 다익스트라는 양수 간선이 하나라도 존재하면 종료를 보장할 수 없습니다. 이는 사이클의 존재 여부와 관련이 없습니다."

와 동치입니다.

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

문제

문제

출처

ICPC

다익스트라 말고 다르게 풀었습니다..

alohajihwan 7년 전 0

wowoto9772 7년 전 1

koosaga 7년 전 1

alohajihwan 7년 전 2

ainch96 7년 전 0

koosaga 7년 전 2

alohajihwan 7년 전 0

alohajihwan 7년 전 0

koosaga 7년 전 2

alohajihwan 7년 전 0

koosaga 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말