[백준] 124-번 : 노드사이의 거리 Gold5(골드5) - JAVA[자바]

[Gold V] 노드사이의 거리 - 1240

문제 링크

성능 요약

메모리: 51564 KB, 시간: 292 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자

2023년 12월 12일 11:34:45

문제 설명

 N$N$개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N$N$과 거리를 알고 싶은 노드 쌍의 개수 M$M$이 입력되고 다음 N−1$N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M$M$개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

 M$M$개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

 

풀이 방법

1. 각 노드를 연결시켜주는 ArrayList배열을 생성

2. Node 클래스를 삽입해줌. (갈 수 있는 노드 위치, 가중치)

3. bfs를 통해서 갈 수 있는 곳 전부 비교(넣은 곳은 visit표시)

4. 만약 도착지가 goal과 같다면 dist에다가 가중치를 넣어주고 break;

5. return 한 dist값을 StringBuilder에 추가

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

public class Main {
    static class Node{
        int destination;
        int dist;

        public Node(int destination, int dist){
            this.destination = destination;
            this.dist = dist;
        }
    }
    static List<Node>[] lists;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        lists = new ArrayList[a + 1];
        for(int i = 1; i <= a; i++){
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < a - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            // 이어주고 가중치를 삽입
            lists[x].add(new Node(y, v));
            lists[y].add(new Node(x, v));
        }
        for (int i = 0; i < b; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int goal = Integer.parseInt(st.nextToken());
            // 방문 배열을 초기화
            visit = new boolean[a + 1];
            sb.append(dfs(start, goal) + "\n");
        }
        System.out.println(sb);
    }

    private static int dfs(int pos, int goal) {
        // 선언 후 시작 노드를 넣어주고 방문체크
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(pos, 0));
        visit[pos] = true;

        int dist = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            // 불러온 노드가 목표와 같다면 값 삽입 후 break;
            if (node.destination == goal) {
                dist =  node.dist;
                break;
            }

            // 현재 노드에서 갈 수 있는 노드들을 전부 불러줌
            for(Node tmp:lists[node.destination]){
                // 방문하지 않은 노드만 로직 실행
                if (!visit[tmp.destination]) {
                    // 현재 가중치 + 새로운 가중치 후 큐에 삽입
                    q.offer(new Node(tmp.destination, node.dist + tmp.dist));
                    // 방문 처리
                    visit[tmp.destination] = true;
                }
            }
        }
        return dist;
    }
}