백준 1240번. 노드사이의 거리 (Java)

1. 문제 조건

2. 아이디어

주어진 예제 입력을 살펴보면 아래와 같다. 

 

인접행렬은 메모리 차지를 많이 할 수 있다고 생각되어 인접리스트로 구현하려고 했다. 또한, 두 노드 사이의 거리를 구하기 위해서는 간선 사이에 양방향 통행이 가능해야 하므로, 부모, 자식 상관 없이(문제에서 부모 자식을 구분할 수도 없었다.) 양 쪽 노드의 자식 노드 list에 노드를 모두 추가해줘야겠다고 생각했다. 이 때, 거리도 함께 기억해야 하므로 class를 생성하여 관리하고자 했다.

 

문제풀이를 하는 방식은 BFS와 DFS를 떠올렸다. 단순히 하나의 노드에서 목적지 노드까지 간선을 따라 타고 가기만 하면 되는 문제였기 때문이다. 

 

실제로 두가지 방식으로 구현하여 제출 후 정답처리 되었으며 이 문제는 메모리와 시간복잡도 두가지 모두에서 DFS가 유리했다. 분석한 이유는 아래와 같다. 

 

1. 메모리 사용

• DFS는 재귀 호출을 사용하여 현재 경로의 노드만을 스택에 저장하기 때문에, 한 번에 탐색 경로 상의 노드만 메모리에 유지한다. 특히 트리 구조에서는 사이클이 없어 한 방향으로만 탐색이 진행되므로, DFS의 메모리 사용은 BFS에 비해 절약적이다.
• BFS는 많은 노드가 메모리에 동시에 저장되어야 한다. 따라서 DFS에 비해 메모리 사용이 크다고 볼 수 있다.

2. 시간 복잡도

• DFS는 탐색을 시작한 노드로부터 목표 노드까지의 경로를 찾는 데 있어 불필요한 경로를 일찍 포기하고 다른 경로를 시도한다. 트리에서 두 노드 사이의 경로는 유일하므로, 일단 목표 노드에 도달하면 탐색을 즉시 중단한다.
• BFS는 최단 경로를 찾을 때 유리하지만, 모든 인접 노드를 균등하게 탐색하기 때문에 목표 노드를 찾더라도 모든 가능한 경로를 확인할 때까지 계속 탐색한다. 따라서 이 문제의 경우, DFS보다 더 많은 시간이 소요될 수 있다.

 

3. 구현

package gold5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1240노드사이의거리 {


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static ArrayList<Edge>[] edges;

    static boolean[] visited;

    static int answer;
    public static class Edge{
        int node;
        int distance;

        public Edge(int node, int distance){
            this.distance =distance;
            this.node = node;
        }
    }

    public static void main(String[] args) throws IOException {

        //트리 입력
        input();

        //거리 알고 싶은 노드 입력
        for(int m=0; m<M; m++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());


            answer = 0;
            visited = new boolean[N+1];


            dfs(a,b,0);
//           bfs(a, b);
            sb.append(answer).append("\n");
        }

        System.out.println(sb.toString());



    }

    public static void bfs(int a, int b){

        visited[a] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{a, 0});

        while(!queue.isEmpty()){
            int[] now = queue.poll();

            if(now[0]==b) answer = now[1];
            for(Edge next : edges[now[0]]){
                if(!visited[next.node]){
                    visited[next.node] = true;
                    queue.add(new int[] {next.node, now[1]+next.distance});
                }
            }
        }

    }

    public static void dfs(int now, int end, int distance){
        if(now==end) answer = distance;

        visited[now] = true;
        for(Edge next : edges[now]){
            if(!visited[next.node]){
                dfs(next.node, end, distance+next.distance);
            }
        }
    }

    public static void input() throws IOException {
        st = new StringTokenizer(br.readLine());


        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        edges = new ArrayList[N+1];

        for(int n=0; n<=N; n++){
            edges[n] = 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 d = Integer.parseInt(st.nextToken());

            edges[a].add(new Edge(b, d));
            edges[b].add(new Edge(a, d));

        }

    }
}