백준 - 1719번 택배
https://www.acmicpc.net/problem/1719
접근법
- 다익스트라로 최단거리를 구하기 위해
ArrayList<Point>[] ADJ
배열을 생성함 - 배열에 양방향으로 간선 연결을 해줌
2차원 배열로 하게되면, 연결되어있는지 아닌지 n번 탐색을 해야하는데, arrayList면 size만큼만 탐색하면 되니 시간을 아낄 수 있음
- 각각의 노드를 기준으로 다익스트라 함수를 탐색
path[]
배열로 현재 노드의 앞 노드를 기록해둠- 출력 시, 현재 노드면 -를 출력
그게 아니라면, 현재 노드에서 앞 노드를 찾고, 그게 끝인지 보고 아니면 또 앞 노드, ... 반복하여 출력
소스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static ArrayList<Point>[] ADJ;
static int[][] ans;
static int N, M;
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());
M = Integer.parseInt(st.nextToken());
ADJ = new ArrayList[N+1];
for(int i = 0; i < N+1; i++) {
ADJ[i] = new ArrayList<Point>();
}
ans = new int[N+1][N+1];
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
ADJ[s].add(new Point(e, w));
ADJ[e].add(new Point(s, w));
}
for(int i = 1; i < N+1; i++) {
dijkstra(i);
}
}
public static void dijkstra(int node) {
int[] dist = new int[N+1];
int[] path = new int[N+1];
boolean[] visit = new boolean[N+1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[node] = 0;
Queue<Point> q = new LinkedList<Point>();
q.offer(new Point(node, 0));
while(!q.isEmpty()) {
Point cur = q.poll();
int curNode = cur.node;
int curWeight = cur.weight;
// if(visit[curNode]) continue;
// visit[curNode] = true;
for(int i = 0; i < ADJ[curNode].size(); i++) {
Point newNode = ADJ[curNode].get(i);
if(dist[newNode.node] > curWeight + newNode.weight) {
dist[newNode.node] = curWeight + newNode.weight;
q.offer(new Point(newNode.node, curWeight + newNode.weight));
path[newNode.node] = curNode == node ? newNode.node : curNode;
}
}
}
for(int i = 1; i < N+1; i++) {
if(i == node) System.out.print("- ");
else {
int j = i;
while(j != path[j]) {
j = path[j];
}
System.out.print(j + " ");
}
}
System.out.println();
}
}
class Point{
int node;
int weight;
Point(int node, int weight){
this.node = node;
this.weight = weight;
}
}
Author And Source
이 문제에 관하여(백준 - 1719번 택배), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@upisdown/백준-1719번-택배저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)