[BOJ] 백준 1240. 노드사이의 거리

문제

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

 

 

 

---

풀이

 트리에서의 탐색 문제입니다. Dfs를 이용해서 문제를 해결했습니다.

 

 우선 Arraylist[] 배열에 입력값을 입력받습니다. 이 때, 방향은 양방향 모두 갈 수 있으니 양뱡향으로 입력 받습니다.

 

 그리고 dfs메서드를 통해 시작점부터 탐색을 시작합니다. 한 가지 주의해야할 것은, 거리의 합을 구하는 것에 있습니다. 만약 아래와 같은 입력 값이 주어질 때를 생각해보겠습니다.

 

4 1
1 2 1
2 3 1
2 4 1
1 4

// 정답 
2

 

 이 반례 코드에서 2는 3, 4의 두 방향으로 뻗게 됩니다. 그래서 3으로 보낸 dfs에서 거리의 합에 거리를 더하고, 그것을 바로 4로 보내게 되면 중복해서 값이 들어가게 됩니다. 그래서 한 노드에서 여러 갈래로 뻗는 것을 고려해, dfs 재귀를 보낸 후에 다시 거리의 합을 원상태로 돌려주어야 합니다.

 

 아래는 소스 코드입니다.

---

소스 코드

import java.util.ArrayList;
import java.util.Scanner;

public class B1240_노드사이의거리 {
    static int N, M;
    static ArrayList<Node>[] list;
    static class Node{
        int ed;
        int w;
        Node(int ed, int w){
            this.ed = ed;
            this.w = w;
        }
    }
    static int dist;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        visited = new boolean[N+1];
        list = new ArrayList[N+1];
        for(int i = 0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0;i<N-1;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int w = sc.nextInt();
            list[st].add(new Node(ed,w));
            list[ed].add(new Node(st,w));
        }

        for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            visited = new boolean[N+1];
            dist = 0;
            dfs(st,ed);
        }
    }

    static void dfs(int now, int ed){
        visited[now] = true;
        if(now == ed){
            System.out.println(dist);
            return;
        }
        else{
            for(int i = 0;i<list[now].size();i++){
                int next = list[now].get(i).ed;
                if(!visited[next]) {
                    visited[next] = true;
                    dist += list[now].get(i).w;
                    dfs(next,ed);
                    dist -= list[now].get(i).w;
                }
            }
        }
    }
}