아이디어

• 주어진 그래프가 트리다. 트리는 사이클이 없으므로, 두 점을 잇는 경로가 항상 유일하게 된다. 따라서 이 문제는 외판원 문제가 아닌 단순한 탐색 문제다.
  • 문제에서도 그냥 ‘거리’라고만 명시되어 있다.
• 인접 리스트를 나타내기 위해 Map[] 변수를 만들었다.
  • 인접행렬로 나타내기에는 주어진 그래프가 트리기 때문에 sparce하다고 생각했다. 결론적으로 딱히 상관은 없었다.
  • Map을 Set<Map.Entry>로 보아 key 자리에 이웃 번호를, value 자리에 가중치를 썼다.
• DFS를 이용하였다.
  • 탐색하며 종점(e)를 찾으면 backtracking하며 return 값에 경로 내 간선의 가중치를 누적 합한다.

코드

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static Map<Integer, Integer>[] maps;
    static boolean[] checked;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();

        maps = new Map[n+1];
        for (int i=1; i<=n; i++) {
            maps[i] = new LinkedHashMap<>();
        }

        for (int i=0; i<n-1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int d = sc.nextInt();
            maps[a].put(b, d);
            maps[b].put(a, d);
        }

        for (int i=0; i<m; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();

            checked = new boolean[n+1];
            System.out.println(dfs(s, e));
        }
    }

    static int dfs(int s, int e) {
        if (checked[s])
            return -1;
        if (s == e)
            return 0;
        checked[s] = true;
        for (int nei: maps[s].keySet()) {
            int ret = dfs(nei, e);
            if (ret >= 0)
                return ret + maps[s].get(nei);
        }
        return -1;
    }
}

메모리 및 시간

• 43264 KB / 572 ms

리뷰

• 가중치 있는 그래프를 나타내기 위한 자료구조에 대해 알아보자
  • P.S. 나중에 배운 사실: 목표 노드와 가중치를 가지는 객체를 만들어 리스트를 만들면 된다.