글 읽기 - 왜 이렇게 해도 정답처리가 되는건가요?

le_effort 1년 전 0

문제를 다 풀고 다른 사람들은 어떻게 풀었나 궁금해서 구글링해서 보다가 이해가 안되는 부분이 있어서 질문드립니다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.

하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

이 조건이 주어져서 저는 아래와 같이 생각했습니다.

반드시 지나야하는 정점 2개를 first, second로 뒀을때

first-> 목적지, second-> 목적지 로 간선이 연결되어있지 않아 못가는 경우를 생각해서 돌아오는 로직도 처리 해줬는데요

그림으로 설명하면 다음과 같습니다

이와 같은 경우 출발 -> first -> second -> first -> 출발 -> 목적지로 가야 갈 수 있다고 생각했습니다

마찬가지로 first와 second가 연결되지 않았을 경우엔 출발 ->first -> 출발 -> second 이런 경우의 수를 고려했는데

많은 블로그 풀이를 보면

최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N)
최단거리(1 ~ V2) + 최단거리(V2 ~ V1) + 최단거리(V1 ~ N)

이런 경우만 고려했는데 어떻게 정답 처리가 되는건가요?

"한번 이동했던 간선도 다시 이동할 수 있다" 이 조건을 고려하지 않고 문제를 푼 것 아닌가요?

아래는 제 코드입니다

문제 이해능력이 조금 부족한거 같은데 설명해주시면 감사하겠습니다 !!

import java.io.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n,e;
    static int first,second;    // 꼭 방문 해야 되는 위치
    static int dist[][];
    static boolean visited[][];
    static ArrayList<Node>list[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());


        n = Integer.parseInt(st.nextToken());       // 정점개수
        e = Integer.parseInt(st.nextToken());       // 간선개수
        visited = new boolean[n+1][n+1];
        list = new ArrayList[n+1];
        dist = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=1; i<=n; i++){
            Arrays.fill(dist[i],987654321);
        }

        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            list[a].add(new Node(b,dist));
            list[b].add(new Node(a,dist));
        }

        st = new StringTokenizer(br.readLine());
        first = Integer.parseInt(st.nextToken());
        second = Integer.parseInt(st.nextToken());

        dijkstra(1);
        dijkstra(first);
        dijkstra(second);
        dijkstra(n);

        int ans = 0;
        // 무조건 지나야 하는 정점을 못 지나는 경우
        if(dist[1][first]==987654321 || dist[1][second]==987654321|| dist[1][n]==987654321){
            System.out.println(-1);
            System.exit(0);
        }


        int min = Integer.MAX_VALUE;
        // 1->first->second->n
        min = Math.min(min,dist[1][first]+dist[first][second]+dist[second][n]);
        // 1->second->first->n
        min = Math.min(min,dist[1][second]+dist[second][first]+dist[first][n]);
        // 1->first->1->second->n
        min = Math.min(min,dist[1][first]*2+dist[1][second]+dist[second][n]);

        // 1->first->1->second->1->n
        min = Math.min(min,dist[1][first]*2+dist[1][second]*2+dist[1][n]);
        // 1->second->1->first->n
        min = Math.min(min,dist[1][second]*2+dist[1][first]+dist[first][n]);
        // 1->second->1->first->1->n
        min = Math.min(min,dist[1][second]*2+dist[1][first]*2+dist[1][n]);

        System.out.println(min);

    }
    public static void dijkstra(int idx){
        PriorityQueue<Node>pq = new PriorityQueue<>();
        pq.add(new Node(idx,0));
        dist[idx][idx] = 0;

        while(!pq.isEmpty()){
            Node a = pq.poll();
            if(visited[idx][a.city]) continue;
            visited[idx][a.city] = true;
            for(Node next : list[a.city]){
                if(!visited[idx][next.city] && dist[idx][next.city] > dist[idx][a.city]+ next.dist){
                    dist[idx][next.city] = dist[idx][a.city]+ next.dist;
                    pq.add(new Node(next.city,dist[idx][next.city]));
                }
            }
        }
    }
}
class Node implements Comparable<Node>{

    int city,dist;

    public Node(int city, int dist) {
        this.city = city;
        this.dist = dist;
    }

    public int compareTo(Node o){
        return this.dist - o.dist;
    }
}

Green55 1년 전 1

최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N)
최단거리(1 ~ V2) + 최단거리(V2 ~ V1) + 최단거리(V1 ~ N)

에서 각 최단거리(X~Y)를 구해 줄 때 다른 최단거리에서 밟았던 간선을 중복해서 밟을 수 있도록 구현 해주면 됩니다.

kokosoko59 1년 전 1

first-> 목적지, second-> 목적지 로 간선이 연결되어있지 않아 못가는 경우, 출발 -> first -> second -> first -> 출발 -> 목적지 라는 경로를 따라가야 한다고 말씀해주셨습니다.

네 맞습니다. 하지만 [second -> first -> 출발 -> 목적지] 가 결국 second 에서 목적지로 가는 최단경로 이기 때문에

최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N)

이 경우에 포함됩니다.

또 다른 예시로 들어주신 first와 second가 연결되지 않았을 경우, 출발 ->first -> 출발 -> second -> 목적지 라는 경로가 최적이라면 [first-> 출발 -> second]가 first에서 second로 가는 최단경로 이기 때문에 이 역시

최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N)

에 포함이 됩니다.

le_effort 1년 전 0

아아 이해 됐습니다 감사합니다 ㅎㅎㅎ!!

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

문제

문제

출처

ICPC

왜 이렇게 해도 정답처리가 되는건가요?

le_effort 1년 전 0

Green55 1년 전 1

kokosoko59 1년 전 1

le_effort 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말