[JAVA] 백준 1240 : 노드사이의 거리

문제

1240번: 노드사이의 거리

해결 방법

가중치가 있는 트리의 탐색 문제의 기본이다.

class를 이용해서 다음 방문할 위치와 거리를 입력해두고 탐색하면서 거리를 계속 더 해주면 된다.

탐색은 BFS를 사용했다.

 

간선을 입력할 때 양쪽으로 이동이 가능하게끔 쌍방향으로 리스트에 넣어주어야 한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static ArrayList<Node> list[];
	static boolean visit[];
	

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
        	list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < N - 1; i++) {
        	st = new StringTokenizer(br.readLine(), " ");
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	int cost = Integer.parseInt(st.nextToken());
        	
        	list[start].add(new Node(end, cost));
        	list[end].add(new Node(start, cost));
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine(), " ");
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	sb.append(find(start, end) + "\n");
        }
        System.out.println(sb);
    }
    static int find(int start, int end) {
    	visit = new boolean[N + 1];
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(start, 0));
    	visit[start] = true;
    	
    	int dist = 0;
    	while(!q.isEmpty()) {
    		Node node = q.poll();
    		if (node.next == end) {
    			dist = node.dist;
    			break;
    		}
    		
    		for (Node temp : list[node.next]) {
    			if (!visit[temp.next]) {
    				q.offer(new Node(temp.next, node.dist + temp.dist));
    				visit[temp.next] = true;
    			}
    		}
    	}
    	
    	return dist;
    }
}

class Node {
	int next;
	int dist;
	
	Node (int next, int dist) {
		this.next = next;
		this.dist = dist;
	}
}