[백준] 노드 사이 거리 (1240) - Java, bfs

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

1240번: 노드사이의 거리

[입력]

첫 번째 라인은 노드의 개수와 거리를 알고 싶은 노드의 쌍의 수가 주어진다.

두 번째 라인부터 N-1개의 줄에 노드의 쌍과 거리가 주어진다.

그 다음 라인부터는 거리를 알고 싶은 M개의 노드의 쌍이 주어진다.

 

 

[문제 해결]

• 노드를 양방향 연결을 한다.
• 시작점을 큐에 넣고 방문 처리를 해준다.
• bfs를 돌리면서  인접 노드들의 거리를 계산해준다. 
• 마지막 노드에 도착하면 종료한다.

---

입력을 받고 난 후의 그래프 관계도

---

---

예제 케이스 3 <-> 2

[Java - bfs]

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


public class Main {

    static int distance[][];
    static boolean visited[];
    static int [][] node;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int nodeNum = Integer.parseInt(st.nextToken());
        int wantNum = Integer.parseInt(st.nextToken());

        node = new int [nodeNum+1][nodeNum+1];
        distance = new int[nodeNum+1][nodeNum+1];

        // init Node
        for(int i=0; i<nodeNum-1; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());
            node[a][b] = 1;
            node[b][a] = 1;
            distance[a][b] = dis;
            distance[b][a] = dis;
        }

        // start bfs
        for(int i=0; i<wantNum; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b=  Integer.parseInt(st.nextToken());
            bfs(a, b, nodeNum);
        }
    }

    public static void bfs(int start, int end, int nodeNum){
        Queue<Integer> queue = new LinkedList<>();
        visited = new boolean[nodeNum+1];

        visited[start] = true;
        queue.add(start);
        int ans[] = new int[nodeNum+1];

        while(!queue.isEmpty()){
            int cur = queue.poll();

            for(int i=1; i<=nodeNum; i++){

                if(node[cur][i] == 1 && !visited[i]){       // 만약 연결되어 있고 방문하지 않은 노드이면
                    ans[i] += distance[cur][i] + ans[cur];  // 거리를 갱신해준다.

                    if(i == end){           // 만약 마지막 노드이면 종료
                        System.out.println(ans[end]);
                        return;
                    }

                    queue.add(i);
                    visited[i] = true;
                }
            }
        }

    }



}