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

📖 문제

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

 

 

 

💡  풀이 방식

• BFS

 

1.  인접 리스트를 만들고 N-1개의 연결 정보를 양방향으로 저장한다.

2. M개의 노드 쌍에 대해 첫 번째 노드부터 두 번째 노드까지의 거리를 구한다. (BFS)

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static List<Node>[] graph;
    static boolean[] chk;
    static StringBuilder sb = new StringBuilder();
    
    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());
        M = Integer.parseInt(st.nextToken());
        
        graph = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i++) {
            graph[i] = 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 v = Integer.parseInt(st.nextToken());
            
            // 양방향
            graph[a].add(new Node(b, v));
            graph[b].add(new Node(a, v));
        }
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            chk = new boolean[N+1];
           bfs(a, b);
        }
        System.out.println(sb.toString());
    }
    
    private static void bfs(int start, int end) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(start, 0));
        
        chk[start] = true;
        
        while(!q.isEmpty()) {
            Node now = q.poll();
            
            if(now.idx == end) {
                sb.append(now.v).append("\n");
                return;
            }
            
            for(Node next : graph[now.idx]) {
                if(!chk[next.idx]) {
                    chk[next.idx] = true;
                    q.add(new Node(next.idx, now.v + next.v));    // 거리 갱신 
                }
            }
        }
    }
}
 
class Node {
    int idx, v;
    
    public Node(int idx, int v) {
        this.idx = idx;
        this.v = v;
    }
}
 

 

 

 

 

---

 

 

1회독	2회독	3회독	4회독	5회독
V

---