java 스터디 8주차 - 다익스트라, 플로이드-워셜

1916 최소비용 구하기

📌문제 링크

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

💡 문제 풀이

수업시간에 배운 다익스트라 코드 적용해서 풀었습니다!!

📋코드

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;

public class Main {
	private static class Edge implements Comparable<Edge> {
		int v, w;

		public Edge(int v, int w) {
			super();
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}
		
		
	}
	
    // 오버플로우 방지를 위해 2bit 이동
	private static final int INF = Integer.MAX_VALUE >> 2;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		List<Edge>[] adj = new ArrayList[N+1];
		for (int i = 1; i < N+1; i++) {
			adj[i] = new ArrayList<>();
		}
		
		int from, to, cost; 
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			from = Integer.parseInt(stk.nextToken());
			to = Integer.parseInt(stk.nextToken());
			cost = Integer.parseInt(stk.nextToken());
			
			adj[from].add(new Edge(to, cost));
		}
		
		// 출발점의 도시번호와 도착점의 도시번호
		stk = new StringTokenizer(br.readLine());
		from = Integer.parseInt(stk.nextToken());
		to = Integer.parseInt(stk.nextToken());
		
		Edge[] D = new Edge[N+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		
		// 출발점 : from
		for (int i = 1; i < N+1; i++) {
			if (i == from) {
				D[i] = new Edge(i, 0);
			} else {
				D[i] = new Edge(i, INF);
			}
			
			pq.add(D[i]);
		}
		
		
		boolean[] check = new boolean[N+1];
		
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			
            // 최단경로 갱신
			for (Edge next : adj[edge.v]) {
				if (!check[next.v] && D[next.v].w > D[edge.v].w + next.w) {
					D[next.v].w = D[edge.v].w + next.w;
					pq.remove(D[next.v]);
					pq.add(D[next.v]);
				}
			}
			
			check[edge.v] = true;
		}
		
		System.out.println(D[to].w);
		
	}

}

1238 파티

📌문제 링크

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

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	private static class Edge implements Comparable<Edge> {
		int v, w;

		public Edge(int v, int w) {
			super();
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}

		@Override
		public String toString() {
			return "Edge [v=" + v + ", w=" + w + "]";
		}
		
		
	}
	
	private static final int INF = Integer.MAX_VALUE >> 2;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		stk = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		int X = Integer.parseInt(stk.nextToken());
		
		List<Edge>[] adj = new ArrayList[N+1];
		List<Edge>[] reverseAdj = new ArrayList[N+1];
		for (int i = 1; i < N+1; i++) {
			adj[i] = new ArrayList<>();
			reverseAdj[i] = new ArrayList<>();
		}
		
		int from, to, cost;
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			from = Integer.parseInt(stk.nextToken());
			to = Integer.parseInt(stk.nextToken());
			cost = Integer.parseInt(stk.nextToken());
			
            // 정방향 인접리스트
			adj[from].add(new Edge(to, cost));
            
            // 모든 마을에서 파티로 가는 최단경로를 계산하기 위해 역방향 인접리스트 생성
			reverseAdj[to].add(new Edge(from, cost));
		}
		
		// 파티 장소에서 모든 정점으로의 최단거리
		Edge[] fromX = new Edge[N+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for (int i = 1; i < N+1; i++) {
			if (i == X) {
				fromX[i] = new Edge(i, 0);
			} else {
				fromX[i] = new Edge(i, INF);
			}
			
			pq.add(fromX[i]);
		}
		
		
		boolean[] check = new boolean[N+1];
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			
			for (Edge next : adj[edge.v]) {
				if (!check[next.v] && fromX[next.v].w > fromX[edge.v].w + next.w) {
					fromX[next.v].w = fromX[edge.v].w + next.w;
					pq.remove(fromX[next.v]);
					pq.add(fromX[next.v]);
				}
			}
			
			check[edge.v] = true;
		}
		
		
		// 모든 정점에서 파티 장소로 가는 최단거리 (방향을 뒤집은 인접리스트 사용)
		pq.clear();
		Edge[] toX = new Edge[N+1];
		for (int i = 1; i < N+1; i++) {
			if (i == X) {
				toX[i] = new Edge(i, 0);
			} else {
				toX[i] = new Edge(i, INF);
			}
			
			pq.add(toX[i]);
		}
		
		Arrays.fill(check, false);
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			
			for (Edge next : reverseAdj[edge.v]) {
				if (!check[next.v] && toX[next.v].w > toX[edge.v].w + next.w) {
					toX[next.v].w = toX[edge.v].w + next.w;
					pq.remove(toX[next.v]);
					pq.add(toX[next.v]);
				}
			}
			
			check[edge.v] = true;
		}
		
		
		int max = 0;
		for (int i = 1; i < N+1; i++) {
			max = Math.max(max, toX[i].w + fromX[i].w);
		}
		
		System.out.println(max);
		
	}

}

11404 플로이드

📌문제 링크

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

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	private static final int INF = Integer.MAX_VALUE >> 2;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			Arrays.fill(map[i], INF);
		}
		
		int to, from, cost;
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			from = Integer.parseInt(stk.nextToken()) - 1;
			to = Integer.parseInt(stk.nextToken()) - 1;
			cost = Integer.parseInt(stk.nextToken());
			
			map[from][to] = Math.min(map[from][to], cost);
			
		}
		
		for (int k = 0; k < N; k++) { // 경유지
			for (int i = 0; i < N; i++) { // 출발지
				if (i==k) continue;
				for (int j = 0; j < N; j++) { // 도착지
					if (i == j || j==k) continue;
					
					if (map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == INF) sb.append(0).append(" ");
				else sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.print(sb);
		
	}

}

1956 운동

📌문제 링크

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

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	private static final int INF = Integer.MAX_VALUE >> 2;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		stk = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(stk.nextToken());
		int E = Integer.parseInt(stk.nextToken());
		
		int[][] map = new int[V][V];
		for (int i = 0; i < V; i++) {
			Arrays.fill(map[i], INF);
		}
		
		int from, to, cost;
		for (int i = 0; i < E; i++) {
			stk = new StringTokenizer(br.readLine());
			
			from = Integer.parseInt(stk.nextToken()) - 1;
			to = Integer.parseInt(stk.nextToken()) - 1;
			cost = Integer.parseInt(stk.nextToken());
			
			map[from][to] = cost;
		}
		
		for (int k = 0; k < V; k++) { // 경유지
			for (int i = 0; i < V; i++) { // 출발지
				if (i == k) continue;
				for (int j = 0; j < V; j++) { // 도착지
					if (j == k || i == j) continue;
					
					if(map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
				}
			}
		}
		
		
		int ans = INF;
		
		for (int i = 0; i < V; i++) {
			for (int j = i+1; j < V; j++) {
				ans = Math.min(ans, map[i][j] + map[j][i]);
			}
		}
		
		if (ans == INF) System.out.println(-1);
		else System.out.println(ans);
	}

}