본문 바로가기

OJ

[BOJ] 1240 노드사이의 거리 (JAVA)

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

 

1240번: 노드사이의 거리

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

www.acmicpc.net

단순하게 생각해도 되는 문제입니다.

bfs를 한 번 돌고나서 visited를 초기화 하거나 false로 fill하는 게 중요합니다.

 

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static boolean[] visited;
	static ArrayList<int[]>[] list;
	
	public static void main(String[] args) throws Exception {
		
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			list[from].add(new int[] { to, cost });
			list[to].add(new int[] { from, cost });
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			bfs(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		System.out.print(sb.toString());
		
	}
	
	static void bfs(int from, int to) {
		
		Queue<int[]> q = new LinkedList<>();
		visited = new boolean[N + 1];
		q.offer(new int[] { from, 0 });
		
		while(!q.isEmpty()) {
			
			int[] now = q.poll();
			
			if(now[0] == to) {
				
				sb.append(now[1]).append("\n");
				return;
				
			}
			
			for (int[] next : list[now[0]]) {
				
				if(!visited[next[0]]) {
					
					q.offer(new int[] { next[0], now[1] + next[1] });
					visited[next[0]] = true;
					
				}
				
			}
			
		}
		
	}
	
}

'OJ' 카테고리의 다른 글