백준 No.18223 민준이와 마산 그리고 건우- JAVA

문제 

종강을 맞은 민준이는 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이었다.

그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 처한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다.

 

지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다. 정점은 1~V까지 있다. 건우는 P번 정점에 있다.

그리고 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다.

중복되는 간선과 자기 자신을 가리키는 간선은 존재하지 않는다.

아래와 같은 그래프가 있을 때,

위의 경우는 최단경로가 두 가지 있다.

1→3→4→5→6 또는 1→3→5→6 이다. 이것 중에서 건우가 있는 곳, 즉 4번 정점이 포함된 최단 경로가 있으므로 이 경우에는 민준이가 건우를 도울 수 있다.

민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.

어쩌면 지킬 수도 있는 민준이의 우정을 위해 우리가 도와주자!

 

https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

6 7 4
1 2 1
1 3 1
2 3 10
3 4 1
3 5 2
4 5 1
5 6 1

 

 

풀이

- 다른 문제 풀이도 있을 수 있지만 나는 1번에서 출발해서  P로 가는 최단 경로와 V로 가는 최단 경로를 구한 다음 

P번에서 다시 시작해 최단 경로를 구했다. 그리고 1번에서 P로 가는 최단 경로와 P번에서 V번으로 가는 최단 경로를 더한 값과 1번에서 P번으로 가는 최단경로가 같다면 건우를 구한다고 가정하고 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Node>> grpah = new ArrayList<>();

    static int dist[];
    static int V,E,P;

    static boolean solution = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        dist = new int[V+1];
        for (int i = 0; i <= V ; i++) {
            grpah.add(new ArrayList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            grpah.get(start).add(new Node(end,cost));
            grpah.get(end).add(new Node(start,cost));
        }

        djs(1);
        int tempD = dist[V];
        int temp = dist[P];
        djs(P);
        int temp2 = dist[V];


        if(tempD == (temp + temp2)){
            System.out.println("SAVE HIM");
        }else{
            System.out.println("GOOD BYE");
        }

    }


    static void djs(int start){
        Arrays.fill(dist,Integer.MAX_VALUE);

        PriorityQueue<Node> queue = new PriorityQueue<>((o1,o2) -> {
           return o1.cost - o2.cost;
        });

        queue.add(new Node(start,0));
        dist[start] = 0;

        while (!queue.isEmpty()){
            Node now = queue.poll();

            for(Node next : grpah.get(now.vertex)){
                if(dist[next.vertex] > dist[now.vertex] + next.cost){
                    dist[next.vertex] = dist[now.vertex] + next.cost;
                    queue.add(new Node(next.vertex,dist[next.vertex]));
                }
            }
        }
    }



    static class Node{
        int vertex;
        int cost;

        public Node(int vertex,int cost){
            this.vertex = vertex;
            this.cost = cost;
        }
    }
}