다익스트라
✨start 노드와 모든 노드간 거리 탐색, 최단거리를 저장하는 배열 dist[]
✨edge는 모두 양수
✨시간복잡도 O(ElogV)
🪄시간초과를 대비하여 되도록이면 buffer를 사용하도록 하자
1. 인접리스트로 그래프 구현
2. 최단거리 배열 초기화
3. 값이 가장 작은 노드 고르기
4. 최단거리 배열 업데이트
Min(현재 선택한 노드의 최단거리 배열 값+가중치, 연결 노드의 최단거리 배열 값)
한번 선택된(방문한) 노드는 다시 선택되지 않도록 체크하는 배열이 필요: check[]
백준 1753 최단경로
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
import java.io.*;
import java.util.*;
class Edge implements Comparable<Edge>{
int vertex, value;
Edge(int vertex, int value){
this.value = value;
this.vertex = vertex;
}
public int compareTo(Edge e) {
if(this.value > e.value) return 1;
else return -1;
}
}
public class Main {
static int V,E,K;
static int dist[];
static boolean check[];
static ArrayList<Edge> li[];
static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); //정점의 개수
E = Integer.parseInt(st.nextToken()); //간선의 개수
K = Integer.parseInt(br.readLine()); //시작노드
//초기화
dist = new int [V+1];
check = new boolean [V+1];
li = new ArrayList[V+1];
for(int i = 1; i <= V; i++) {
li[i] = new ArrayList<Edge>();
}
for(int i = 0; i <= V; i++) {
dist[i] = Integer.MAX_VALUE; //Arrays.fill()을 사용해도 됨
}
for(int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()); //시작
int v = Integer.parseInt(st.nextToken()); //종료
int w = Integer.parseInt(st.nextToken()); //가중치
li[u].add(new Edge(v, w));
}
pq.add(new Edge(K, 0));
dist[K] = 0; //시작점
while(!pq.isEmpty()) {
Edge current = pq.poll();
int curV = current.vertex;
if(check[curV]) continue;
check[curV] = true;
for(int i = 0; i < li[curV].size(); i++) {
Edge tmp = li[curV].get(i);
int nxt = tmp.vertex;
int value = tmp.value;
if(dist[nxt] > dist[curV] + value) {
dist[nxt] = value+ dist[curV]; //업데이트
pq.add(new Edge(nxt, dist[nxt]));
}
}
}
for(int i = 1; i <= V; i++) {
if(check[i]) System.out.println(dist[i]);
else System.out.println("INF");
}
}
}
백준 1916 최소비용 구하기
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
int target, cost;
Node(int target, int cost){
this.target = target;
this.cost = cost;
}
public int compareTo(Node n) {
return cost - n.cost;
}
}
public class Main {
static int N, M;
static int start, end;
static int dist[];
static boolean check[];
static ArrayList<Node> li[];
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;
N = Integer.parseInt(br.readLine()); //도시의 개수
M = Integer.parseInt(br.readLine()); //버스의 개수
//초기화
dist = new int [N+1];
check = new boolean [N+1];
li = new ArrayList[N+1];
for(int i = 0; i <= N; i++) {
li[i] = new ArrayList<Node>();
}
Arrays.fill(dist, Integer.MAX_VALUE);
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 c = Integer.parseInt(st.nextToken()); //가중치(비용)
li[s].add(new Node(e, c));
}
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken()); //출발점 도시번호
end = Integer.parseInt(st.nextToken()); //도착
bw.write(sol(start, end)+"\n");
bw.flush();
bw.close();
}
public static int sol(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
dist[start] = 0;
while(!pq.isEmpty()) {
Node current = pq.poll();
int cur = current.target;
if(!check[cur]) {
check[cur] = true;
for(Node n : li[cur]) {
if(!check[n.target] && dist[n.target] > dist[cur]+n.cost) {
dist[n.target] = dist[cur]+n.cost;
pq.add(new Node(n.target, dist[n.target]));
}
}
}
}
return dist[end];
}
}
6248
6248번: Bronze Cow Party
One cow from each of N farms (1 <= N <= 1000) conveniently numbered 1..N is attending the big cow party to be held at farm #X (1 <= X <= N). Each of M (1 <= M <= 100,000) bidirectional roads connects one farm to another. It is always possible to travel fro
www.acmicpc.net
package baekjoon;
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
int node;
int time;
public Node(int node, int time) {
this.node = node;
this.time = time;
}
public int compareTo(Node o) {
return Integer.compare(this.time, o.time);
}
}
public class tmp {
static final int INF = Integer.MAX_VALUE;
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()); // 도로의 개수
int X = Integer.parseInt(st.nextToken()); // 농장 번호
//초기화
List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(st.nextToken());
graph.get(A).add(new Node(B, T));
graph.get(B).add(new Node(A, T));
}
//배열 리턴
int[] distance = dijkstra(graph, X);
int maxTime = 0;
for (int i = 1; i <= N; i++) {
if (i != X) {
int totalTime = distance[i] + dijkstra(graph, i)[X];
maxTime = Math.max(maxTime, totalTime);
}
}
bw.write(Integer.toString(maxTime));
bw.newLine();
br.close();
bw.close();
}
private static int[] dijkstra(List<List<Node>> graph, int start) {
int[] dist = new int[graph.size()];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int cur = current.node;
int curTime = current.time;
if (curTime > dist[cur]) continue;
for (Node f : graph.get(cur)) {
if (curTime + f.time < dist[f.node]) {
pq.add(new Node(f.node, dist[f.node]));
}
}
}
return dist;
}
}
'Algorithms > study log' 카테고리의 다른 글
[java] 플로이드-워셜 알고리즘 (0) | 2024.02.06 |
---|---|
[java] 벨만포드 알고리즘 (0) | 2024.02.06 |
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |
[java] 이분탐색 (2) | 2024.01.12 |
[Algorithm] Greedy 그리디 알고리즘 (1) | 2023.12.27 |