[백준] 15971: 두 로봇 - JAVA

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

 

풀이

두 로봇이 서로 통신하기 위해서는 서로 인접한 지역에 있어야 한다.

a구역에 있는 로봇과 b구역의 로봇에 서로 통신할 수 있는 지역으로 이동할 때 이동해야하는 거리의 최솟값을 구해야 한다.

생각한 풀이방법은 먼저 a지역에서 b지역까지 이동하고, 그 중 거리가 가장 큰 구간을 빼주는 것이다.

dfs를 통해 int배열에 이동한 구역의 거리를 기록했고, 이 배열을 방문처리용도로 사용했다.

 

---

 

메모리: 80360KB
시간: 1008ms
언어: Java 11

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

public class Main {
    static class Node {
        int v;
        int cost;

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

    static int start, end, answer;
    static ArrayList<ArrayList<Node>> list;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Node(b, c));
            list.get(b).add(new Node(a, c));
        }

        answer = Integer.MAX_VALUE;
        visited = new int[n + 1];
        dfs(start);

        System.out.println(answer);
    }

    private static void dfs(int idx) {
        if (idx == end) {
            int max = 0;
            int sum = 0;
            for (int i = 0; i < visited.length; i++) {
                sum += visited[i];
                max = Math.max(max, visited[i]);
            }
            answer = Math.min(answer, sum - max);

            return;
        }

        for (Node next : list.get(idx)) {
            if (visited[next.v] > 0) {
                continue;
            }

            visited[next.v] = next.cost;
            dfs(next.v);
            visited[next.v] = 0;
        }
    }

}