[백준, Java] 15971번, 두 로봇(다익스트라)

문제 링크

15971번: 두 로봇

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. 두 동굴을 연결하는 통로가 존재하며, 통로는 거리가 존재합니다.

2. 두 개의 드론은 동굴 내 같은 통로 위에 위치해야 서로 통신할 수 있습니다.

3. 두 드론의 위치가 주어질 때 통신하는 거리의 최소합을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 다익스트라을 이용해서 최단 거리를 탐색합니다.

 

3. 최단 거리에 포함된 가장 큰 거리를 뺀 거리를 결과로 출력합니다.

 

 

드론 통신하기

 

다익스트라를 통해서 두 드론의 위치를 기준으로 최단 거리를 구합니다.

 

다익스트라를 진행할 때에 해당 경로에 포함된 통로의 거리중 가장 큰 거리를 저장합니다.

 

최단 거리를 구한 뒤, 가장 큰 거리를 뺀 값이 최소 거리가 됩니다.

 

 Why??

 

드론이 통신할 때 가장 큰 거리를 가진 통로에서 진행한다면, 해당 통로의 거리를 지나지 않아도 되기 때문입니다.

 

※예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 5

 

S : 1

 

E : 5

 

 

 

동굴과 통로에 따른 그래프 형성

 

 

 

2. 다익스트라을 이용해서 최단 거리를 탐색합니다.

 

S드론을 기준으로 E드론까지 도착하는 최단 거리 탐색

 

 

 

 

이동한 거리 : 1

 

최장 거리 통로 : 1

 

 

 

 

이동한 거리 : 3

 

최장 거리 통로 : 2

 

이동한 거리 : 6

 

최장 거리 통로 : 3

 

 

 

이동한 거리 : 10

 

최장 거리 통로 : 4

 

3. 최단 거리에 포함된 가장 큰 거리를 뺀 거리를 결과로 출력합니다.

 

이동한 거리 : 10

 

최장 거리 통로 : 4

 

최단 거리 : 10 - 4 = 6

 

6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 로봇 및 통로의 정보를 띄어쓰기 기준 저장합니다.
• 두 드론의 위치를 기준으로 search함수를 통해 최단 거리를 구합니다.
• 최단 거리를 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 다익스트라를 통해서 최단 거리를 구합니다.
• search함수는 최단 거리를 반환할 때 경로 포함 최장 거리 통로를 줄입니다.

결과코드

import java.io.*;
import java.util.*;


public class Main {
    //터널 정보 클래스
    static class Tunnel{
        //다음값, 거리
        int to, cost;
        Tunnel(int to, int cost){
            this.to = to;
            this.cost = cost;
        }
    }
    //다익스트라를 위한 클래스
    static class Info implements Comparable<Info>{
        //idx : 현재, cost : 이동한 거리, max : 최장 통로 거리
        int idx, cost, max;
        Info(int idx, int cost, int max){
            this.idx = idx;
            this.cost = cost;
            this.max = max;
        }
        //이동한 거리 기준 오름차순 정렬
        @Override
        public int compareTo(Info o) {
            return this.cost - o.cost;
        }
    }
    //터널 정보 저장 리스트
    static List<List<Tunnel>> tunnels = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        //터널 리스트 초기화
        for(int i=0;i<=N;i++){
            tunnels.add(new ArrayList<>());
        }
        //터널 정보 저장
        for(int i=1;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            //양방향 터널
            tunnels.get(from).add(new Tunnel(to,cost));
            tunnels.get(to).add(new Tunnel(from,cost));
        }
        //다익스트라를 통한 최단거리 구하기
        int result = search(S, E, N);
        //최단거리 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라를 통해 최단 거리를 구합니다.
    static int search(int start, int end, int N){
        //다익스트라를 위한 우선순위 큐
        PriorityQueue<Info> pq = new PriorityQueue<>();
        pq.add(new Info(start,0,0));
        boolean[] visited = new boolean[N+1];
        visited[start] = true;
        //다익스트라 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //가장 먼저 도착 드론에 왔을 때
            if(cur.idx == end){
                //이동한 거리 - 통로 최장 거리
                return cur.cost - cur.max;
            }
            //주변 통로 탐색
            for(Tunnel tunnel : tunnels.get(cur.idx)){
                if(!visited[tunnel.to]){
                    visited[tunnel.to] = true;
                    pq.add(new Info(tunnel.to, cur.cost + tunnel.cost, Math.max(cur.max, tunnel.cost)));
                }
            }
        }
        return 0;
    }
}