[백준] 알고리즘 분류(트리,JAVA)1240번, 노드사이의 거리

문제 링크

1240번: 노드사이의 거리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 입력되는 정보에는 각 노드 사이의 거리를 받습니다.

2. M개의 노드 쌍의 거리를 결과로 출력합니다.

3. N개의 노드로 이루어져 있는 트리입니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS탐색을 진행하여 M개의 노드 쌍의 거리를 구합니다.

 

3. 노드 쌍의 거리를 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

 

2 1 2
4 3 2
1 4 3

※ 저는 트리의 형태롤 보기 좋게 임의로 1번 노드를 Root 노드로 표현한 것입니다.

M : 2

 

1 2
3 2

 

2. BFS탐색을 진행하여 M개의 노드 쌍의 거리를 구합니다.

 

1 2

1 - 2 : 2

3 2

3 - 4 - 1 - 2 : 7

 

3. 노드 쌍의 거리를 결과로 출력합니다.

 

2

7

결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리 정보를 띄어쓰기 기준 나누었습니다.
• 트리의 정보를 이용하여 노드끼리 연결된 관계를 정의합니다.
• search함수를 M개의 노드 쌍의 거리를 구하였습니다.
• 노드 쌍의 거리들을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 각 노드의 거리를 구하는 BFS함수입니다.

 

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


public class Main {
    //트리 노드 정보 저장 클래스
    static class node{
        int next, length;
        public node(int next, int length){
            this.next = next;
            this.length = length;
        }
    }
    static ArrayList<ArrayList<node>> tree = new ArrayList<>();	//트리 정보 저장 리스트
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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());
        for(int i=0;i<=N;i++)
            tree.add(new ArrayList<>());
        //입력되는 트리 정보 저장
        for(int i=1;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            tree.get(a).add(new node(b, w));
            tree.get(b).add(new node(a, w));
        }
        //M개의 노드 쌍 거리 구하기
        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(search(a, b, N) + "\n");	//거리 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //노드 쌍 거리 구하는 BFS함수
    static int search(int start, int end, int n){
        Queue<node> q = new LinkedList<>();		//BFS에 사용할 Queue
        boolean[] visited = new boolean[n+1];	.//노드 방문 확인 배열
        visited[start] = true;	//시작 노드 방문 확인
        q.add(new node(start, 0));	//시작 노드 Queue 저장
        while(!q.isEmpty()){
            node cur = q.poll();
            if(cur.next == end)		//목적지 도착시
                return cur.length;
            //현재 노드 연결된 주변 노드 탐색
            for(node next : tree.get(cur.next)){
                if(!visited[next.next]){
                    visited[next.next] = true;
                    q.add(new node(next.next, cur.length + next.length));
                }
            }
        }
        return -1;
    }
}