[백준] 1240번 노드사이의 거리(java)

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

1240번: 노드사이의 거리

dfs를 사용하여 쉽게 풀 수 있다.

 

핵심

dfs를 사용하면 쉽게 풀 수 있다. 가중치가 있기 때문에 Node라는 클래스를 만들어서 활용하였다.

 

 

정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main{
    static List<Node>[] nodes;
    static boolean[] visited;
    static int distance;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nAndM = br.readLine().split(" ");
        int N = Integer.parseInt(nAndM[0]);
        int M = Integer.parseInt(nAndM[1]);
        nodes = new ArrayList[N + 1];
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) nodes[i] = new ArrayList<>();

        for (int i = 0 ; i < N-1; i++){
            String[] info = br.readLine().split(" ");
            int from = Integer.parseInt(info[0]);
            int to = Integer.parseInt(info[1]);
            int value = Integer.parseInt(info[2]);
            nodes[from].add(new Node(to, value));
            nodes[to].add(new Node(from, value));
        }

        for (int i = 0; i < M; i++){
            distance = 0 ;
            visited = new boolean[N + 1];
            String[] choiceNode = br.readLine().split(" ");
            int from = Integer.parseInt(choiceNode[0]);
            int to = Integer.parseInt(choiceNode[1]);
            visited[from] = true;
            dfs(from,to,0);
            sb.append(distance).append("\n");
        }
        System.out.println(sb);
    }

    public static void dfs(int start,int end, int sum){
        if (start == end){
            distance = sum;
            return;
        }
        for (Node node : nodes[start]) {
            if (!visited[node.link]){
                visited[node.link] = true;
                dfs(node.link, end, sum + node.value);
                visited[node.link] = false;
            }
        }
    }
}

class Node{
    public int link;
    public int value;

    public Node(int link, int value) {
        this.link = link;
        this.value = value;
    }
}

해설

성능을 위해서 Scanner가 아닌 BufferedReader를 사용하였다.

앞서 말했듯이 가중치와 연결된 노드의 정보가 필요하므로 Node클래스를 만들어주었다.

일반적인 dfs를 사용하여 풀었다. 방문여부를 체크하여 아직 방문하지 않은 곳 인지 확인해 주었다.

현재 탐색하는 노드가 목표하는 노드에 도달했다면 distance를 업데이트한다.

성능을 위해 케이스별로 print를 하는 것이 아닌 StringBuilder를 사용하여 한번에 처리해 주었다.

 

 

배운 점

이전에도 이와 비슷한 문제를 많이 풀어보았고, 단순한 문제이기에 쉽게 풀 수 있을 줄 알았다.

하지만 원하는 값이 계속해서 나오지 않았고, 이유는 초기값 세팅 과정인

int from = Integer.parseInt(info[0]);
int to = Integer.parseInt(info[1]);
int value = Integer.parseInt(info[2]);

이 부분을 모두 info [0]으로 두었기 때문이었다. 

습관적으로 위 코드를 복사하여 빠르게 수정하는 과정에서 이러한 실수가 발생하였다.

복붙을 할 경우 오타나 실수의 확률이 급증하기 때문에 이러한 부분을 잘 체크해야겠다.