15971 두 로봇

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

15971번: 두 로봇

답을 도출하는 과정을 잘 이해하지 못하여 틀린 문제이다.

다른 사람의 코드를 참고하긴 했지만 여러모로 아쉬웠다.

 

내가 처음에 접근했던 방식은 로봇이 위치한 두 정점에서 각각 BFS를 수행하여 교차되는 지점들을 모두 찾아 경로의 합을 구하는 방식이었다. 그런데, 틀렸다고 나와서 당황했다;;

 

사실 정답은 최단 경로 가중치의 합에서 가장 긴 가중치만 빼주면 된다. 이를 위한 탐색 방법은 bfs, dfs, 다익스트라 중 아무거나 사용해도 된다.

 

코드보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Pair{
    Integer y, x;
    public Pair(Integer y, Integer x){
        this.y = y;
        this.x = x;
    }
    public Integer first(){
        return this.y;
    }
    public Integer second(){
        return this.x;
    }
}
public class Main {
    static int N, Start, End, answer = 1000000000;
    static boolean[] visited = new boolean[100001];
    static ArrayList<Pair>[] graph;
    public static void dfs(int cur, int sum, int max_w){
        if(cur == End){
            answer = sum - max_w;
            return;
        }
        visited[cur] = true;
        for(int i = 0; i < graph[cur].size(); i++){
            int next = graph[cur].get(i).first();
            int nextCost = sum + graph[cur].get(i).second();
            if(visited[next] == false){
                dfs(next, nextCost, Math.max(max_w, graph[cur].get(i).second()));
            }
        }
    }
    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());
        Start = Integer.parseInt(st.nextToken());
        End = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N + 1];
        for(int i = 0; i < N + 1; i++)
            graph[i] = new ArrayList<>();
        for(int i = 0; i < N - 1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            graph[s].add(new Pair(e, d));
            graph[e].add(new Pair(s, d));
        }
        dfs(Start, 0, 0);
        System.out.println(answer);
    }
}