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' 카테고리의 다른 글
[BOJ] 1806 부분합 (JAVA) (0) | 2022.12.27 |
---|---|
[BOJ] 1726 로봇 (JAVA) (0) | 2022.12.26 |
[BOJ] 16441 아기돼지와 늑대 (JAVA) (0) | 2022.12.23 |
[BOJ] 23254 나는 기말고사형 인간이야 (JAVA) (2) | 2022.12.22 |
[BOJ] 17834 사자와 토끼 (JAVA) (0) | 2022.12.20 |