백준 - 1719번 택배 - java

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

 

접근법

1. 다익스트라로 최단거리를 구하기 위해 ArrayList<Point>[] ADJ 배열을 생성함
2. 배열에 양방향으로 간선 연결을 해줌2차원 배열로 하게되면, 연결되어있는지 아닌지 n번 탐색을 해야하는데, arrayList면 size만큼만 탐색하면 되니 시간을 아낄 수 있음
3. 각각의 노드를 기준으로 다익스트라 함수를 탐색
4. path[] 배열로 현재 노드의 앞 노드를 기록해둠
5. 출력 시, 현재 노드면 -를 출력
   그게 아니라면, 현재 노드에서 앞 노드를 찾고, 그게 끝인지 보고 아니면 또 앞 노드, ... 반복하여 출력

소스

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;
	}
}