BOJ 1504번 :: 특정한 최단 경로

#문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

#작성 코드

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
 
void input(){
    //  정점의 개수, 간선의 개수 입력 
    scanf("%d %d", &N, &E);
    // 그래프 입력 
    for(int i=0; i<E; i++){
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        // 양방향 그래프! 
        node[start].push_back(make_pair(end, cost));
        node[end].push_back(make_pair(start, cost));
    }
    // 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 
    scanf("%d %d", &one, &two);
}
 
int dijkstra(int start, int end){
    // start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화. 
    long long int shortest[801];
    fill_n(shortest, 801, INF);
    
    priority_queue< pair<int, int> > pq;
    // 우선순위 큐에 시작 정점 push.  
    pq.push(make_pair(0, start));
    shortest[start] = 0; 
    
    while(!pq.empty()){
        // 현재 위치의 정점에 대해 탐색. 
        int now = pq.top().second;
        int nowcost = -pq.top().first;
        pq.pop();
        // 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스 
        if( shortest[now] < nowcost ) continue;
        
        // now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체. 
        for( int i=0; i<node[now].size(); i++){
            int next = node[now][i].first;
            int nextcost = node[now][i].second + nowcost;
            
            if( shortest[next] > nextcost ){
                shortest[next] = nextcost;
                pq.push(make_pair(-nextcost, next));
                // 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다. 
            }
        }
    }
 
    // end까지의 최단거리 갱신이 안되었다면 -1을 리턴한다. 
    if( shortest[end] >= INF ) return -1;
    // end까지의 최단거리가 존재한다면 그 거리를 리턴 
    else    return shortest[end];
}
 
int solve(){
    int startToOne = dijkstra(1, one);
    int startToTwo = dijkstra(1, two);
    int oneToTwo = dijkstra(one, two);
    int twoToEnd = dijkstra(two, N);
    int oneToEnd = dijkstra(one, N);
    int result1=0, result2=0;
    bool flag1 = true, flag2 = true;
    // 경로 중 하나라도 최단거리를 찾지 못하는 경로가 있다면 -1을 출력한다. 
    // 경로 1번 : 1->one->two->N
    if( startToOne==-1 || oneToTwo==-1 || twoToEnd==-1 ){
        flag1 = false;
    }
    // 경로 2번 : 1->two->one->N
    if( startToTwo==-1 || oneToTwo==-1 || oneToEnd==-1 ){
        flag2 = false;
    }
 
    result1 = startToOne+oneToTwo+twoToEnd;        // 경로1번 결과 
    result2 = startToTwo+oneToTwo+oneToEnd;        // 경로2번 결과 
 
    // 경로 1번, 경로 2번 모두 불가능 할 때 
    if( !flag1 && !flag2 ){
        return -1; 
    }
    // 경로 1만 가능할때 
    else if( flag1 && !flag2 ){
        return result1;
    }
    // 경로 2만 가능할때 
    else if( flag2 && !flag1){
        return result2;
    }
    // 경로 1과 2 모두 가능할 때 
    else{
        return min(result1, result2);
    }
}
int main(){
    input();
    printf("%d\n", solve());
    return 0;
}

##

정점의 개수 N이 최대 800개 가능하므로 vector< pair<int, int> > node[801];을 생성한다.

a번 정점에서 b번 정점까지 거리가 c인 양방향 길이 존재 -> node[a]에 {b, c}를 push, node[b]에 {a, c}를 push 한다.

반드시 거쳐야 하는 두 개의 서로 다른 정점을 입력받고 one, two라는 전역변수에 저장한다.

 

맞는 것 같은데, 계속해서 틀렸습니다 판정을 받아서 반례를 게시판에서 찾아 체크했는데 모두 알맞게 나왔다.

문제는, line 90, 94에서 flag1과 flag2에 대해서만 검사하고 !flag2, !flag1 검사를 해주지 않았기 때문에 발생했다.

조건에 대해서는 하나하나 꼭 체크 해주자!!

 

 

#191209 REVIEW

1. line 72~100에서 flag1과 flag2를 체크하는 방법 이외에,

dijkstra()함수에서 INF보다 큰 경우에 -1을 리턴하는 대신 INF 값 그대로를 리턴하게 하고,

result = min(result1, result2) 를 저장해놓고,

result>=INF 라면 -1을 출력하고, 아니라면 result를 출력하게 하는 방법으로 하면 좀 더 간단하게 처리할 수 있겠다.

 

2. dijkstra 함수의 리턴형을 vector<int>로 교체.

startToOne, startToTwo는 원래 코드에서, 같은 결과의 shortest[]배열을 생성하고, 배열 내에서 리턴하는 값의 위치만 달랐다.

dijkstra함수를 start에서 시작해서 다른 모든 정점으로의 최단거리를 계산한 vector를 리턴하도록 해서,

startToOne, startToTwo를 동일한 결과값에서 추출할 수 있도록 변경했다.

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
 
void input(){
    //  정점의 개수, 간선의 개수 입력 
    scanf("%d %d", &N, &E);
    // 그래프 입력 
    for(int i=0; i<E; i++){
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        // 양방향 그래프! 
        node[start].push_back(make_pair(end, cost));
        node[end].push_back(make_pair(start, cost));
    }
    // 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 
    scanf("%d %d", &one, &two);
}
 
vector<int> dijkstra(int start){
    // start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화. 
// vector를 리턴하도록 수정해보았다. 
    vector<int> shortest(801, INF);
    
    priority_queue< pair<int, int> > pq;
    // 우선순위 큐에 시작 정점 push.  
    pq.push(make_pair(0, start));
    shortest[start] = 0; 
    
    while(!pq.empty()){
        // 현재 위치의 정점에 대해 탐색. 
        int now = pq.top().second;
        int nowcost = -pq.top().first;
        pq.pop();
        // 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스 
        if( shortest[now] < nowcost ) continue;
        
        // now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체. 
        for( int i=0; i<node[now].size(); i++){
            int next = node[now][i].first;
            int nextcost = node[now][i].second + nowcost;
            
            if( shortest[next] > nextcost ){
                shortest[next] = nextcost;
                pq.push(make_pair(-nextcost, next));
                // 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다. 
            }
        }
    }
// start부터 다른 모든 정점으로의 최단거리를 저장한 벡터자체를 리턴함. 
    return shortest;
}
 
int solve(){
    vector<int> sStart = dijkstra(1);
    int startToOne = sStart[one];
    int startToTwo = sStart[two];
    
    vector<int> sOne = dijkstra(one);
    int oneToTwo = sOne[two];
    // one->two와 two->one은 동일하므로 한번만 사용. 
    
    vector<int> sEnd = dijkstra(N);
    int twoToEnd = sEnd[two];
    int oneToEnd = sEnd[one];
 
    // 두 가지 경로의 결과값 저장. 
    int result1=0, result2=0;    
    result1 = startToOne+oneToTwo+twoToEnd;        // 경로1번 결과 
    result2 = startToTwo+oneToTwo+oneToEnd;        // 경로2번 결과 
    
//수정한 부분! 
    int result = min(result1, result2);
    if( result>=INF )    return -1;
    else return result;
}
 
int main(){
    input();
    printf("%d\n", solve());
    return 0;
}