[백준] 1240번 Java (그래프, 트리, bfs)

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

문제

풀이

접근법 : 두 노드 사이의 거리를 bfs를 이용하여 구해주면 된다.

static int bfs(int a, int b){
        Queue<int[]> queue = new ArrayDeque<>();
        visited = new boolean[graph.size()];

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

        while (!queue.isEmpty()){
            int [] current = queue.poll();
            int node = current[0];
            int distance = current[1];
            
            if(node == b){
                return distance;    // 노드가 끝 노드일 때 거리 반환
            }

            for (int [] next  : graph.get(node)) {
                int nextNode = next[0];
                int nextDist = next[1];
                
                if(!visited[nextNode]){
                visited[nextNode] = true;
                queue.add(new int[]{nextNode, distance + nextDist});
            }
          }
        }
            return -1;
    }

• 방문하지 않은 노드를 큐에 추가하고 거리를 더해서 함께 넣어준다.
• bfs를 돌리다가 node가 끝 노드일 때 거리를 반환한다.

내 코드

import java.io.*;
import java.util.*;

public class Main {

    static List<List<int[]>> graph;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(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 dist = Integer.parseInt(st.nextToken());
           graph.get(a).add(new int[]{b, dist});
           graph.get(b).add(new int[]{a, dist});
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            bw.write(bfs(a,b) + "\n");
        }
        
        bw.flush();
        bw.close();
    }
    
    static int bfs(int a, int b){
        Queue<int[]> queue = new ArrayDeque<>();
        visited = new boolean[graph.size()];

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

        while (!queue.isEmpty()){
            int [] current = queue.poll();
            int node = current[0];
            int distance = current[1];
            
            if(node == b){
                return distance;    // 노드가 끝 노드일 때 거리 반환
            }

            for (int [] next  : graph.get(node)) {
                int nextNode = next[0];
                int nextDist = next[1];
                
                if(!visited[nextNode]){
                visited[nextNode] = true;
                queue.add(new int[]{nextNode, distance + nextDist});
            }
          }
        }
            return -1;
    }
}