문제
핵심 아이디어
어려운 점, 실수
풀이
DFS
package main.java.com.poogle.BOJ.Q1240;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<Node>[] listArr;
static int result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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());
listArr = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
listArr[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
listArr[start].add(new Node(end, dist));
listArr[end].add(new Node(start, dist));
}
for (int i = 0; i < M; i++) {
result = 0;
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int dest = Integer.parseInt(st.nextToken());
dfs(start, dest, -1, 0);
bw.write(String.valueOf(result));
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
private static void dfs(int start, int dest, int prev, int dist) {
if (start == dest)
result = dist;
for (Node node : listArr[dest]) {
if (node.end != prev) {
dfs(start, node.end, dest, dist + node.dist);
}
}
}
}
class Node {
int end, dist;
public Node(int end, int dist) {
this.end = end;
this.dist = dist;
}
}BFS
package main.java.com.poogle.BOJ.Q1240;
import java.io.*;
import java.util.*;
public class Main {
static List<Node>[] arr;
static int result;
static boolean[] visited;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
arr[start].add(new Node(end, dist));
arr[end].add(new Node(start, dist));
}
for (int i = 0; i < M; i++) {
result = 0;
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
bfs(start, end);
sb.append(result).append("\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
private static void bfs(int start, int end) {
Queue<Node> queue = new LinkedList<>();
visited = new boolean[N + 1];
visited[start] = true;
queue.offer(new Node(start, 0));
while (!queue.isEmpty()) {
Node currNode = queue.poll();
if (currNode.end == end) {
result = currNode.dist;
}
for (Node childNode : arr[currNode.end]) {
if (!visited[childNode.end]) {
queue.offer(new Node(childNode.end, childNode.dist + currNode.dist));
visited[childNode.end] = true;
}
}
}
}
}
class Node {
int end, dist;
public Node(int end, int dist) {
this.end = end;
this.dist = dist;
}
}
다익스트라
package main.java.com.poogle.BOJ.Q1240;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static List<Node>[] arr;
static boolean[] visited;
static int[] dist;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new ArrayList[N + 1];
visited = new boolean[N + 1];
dist = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
arr[start].add(new Node(end, dist));
arr[end].add(new Node(start, dist));
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
Arrays.fill(dist, Integer.MAX_VALUE);
dijkstra(start, end);
}
}
private static void dijkstra(int start, int end) {
PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Node(start, 0));
dist[start] = 0;
while (!priorityQueue.isEmpty()) {
Node curr = priorityQueue.poll();
int now = curr.end;
int nowCost = curr.dist;
if (nowCost > dist[now])
continue;
for (Node node : arr[now]) {
if (dist[node.end] > nowCost + node.dist) {
dist[node.end] = nowCost + node.dist;
priorityQueue.offer(new Node(node.end, nowCost + node.dist));
}
}
}
System.out.println(dist[end]);
}
}
class Node implements Comparable<Node> {
int end, dist;
public Node(int end, int dist) {
this.end = end;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
return this.dist - o.dist;
}
}
