[Baekjoon] 1240_노드사이의 거리

Gold V

문제(출처: https://www.acmicpc.net/problem/1240)

---

< 노드사이의 거리 >

 

문제 풀이

 

노드가 연결된 것을 배열로 표시하여 bfs 탐색을 하면 두 노드 사이의 거리를 구할 수 있다.

 

 

 - my solution (Java)

 

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 _1240_ {
	static int n, arr[][], result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		arr=new int[n+1][n+1];
		for(int i=0; i<n-1; i++) {
			st=new StringTokenizer(bf.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			arr[a][b]=d;
			arr[b][a]=d;
		}
		
		for(int i=0; i<m; i++) {
			st=new StringTokenizer(bf.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			result=0;
			search(a,b);
			System.out.println(result);
		}
	}

	private static void search(int a, int b) {
		boolean[] visited=new boolean[n+1];
		visited[a]=true;
		
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {a,0});
		
		while(!queue.isEmpty()) {
			int start[]=queue.poll();
			for(int i=0; i<n+1; i++) {
				if(i!=start[0] && !visited[i] && arr[start[0]][i]>0) {
					visited[i]=true;
					if(i==b) {
						result=start[1]+arr[start[0]][i];
						break;
					}
					queue.add(new int[] {i, start[1]+arr[start[0]][i]});
				}
			}
			if(result>0) break;
		}
	}
}

 

Main

- 노드의 개수(n), 두 노드 쌍(m) 입력

- 트리 상에 연결된 두 점과 거리를 배열로 입력받음

- 거리를 알고 싶은 노드 쌍 입력받은 후 search 함수 호출

 

search

- visited : 방문 확인 

- Queue : [노드 번호, 거리] 

- queue가 빌 때까지 반복하며 queue에서 값을 뽑아 연결된 노드가 존재하는지 확인 후 아직 방문하지 않은 노드라면 이동한다. 구하려는 노드라면 종료. 구하려는 노드가 아니라면 qeuue에 추가해 준다.

 

---

생각🤔

 

두 노드를 배열로 잘 연결해 준다면 쉽게 구할 수 있다.

 

---