📢 공지합니다
이 게시글은 메인 페이지에 항상 고정되어 표시됩니다.
📌 고정 게시글
최코딩의 개발
[백준] 택배 배송 5972번 (🥇 골드5) 본문
728x90
사이트
https://www.acmicpc.net/problem/5972
문제
분석
실패
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Graph5972 {
static int n;
static int m;
static int[][] num;
static boolean[] visit;
static int sum = 0;
static int min = Integer.MAX_VALUE;
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());
num = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
num[i][j] = -1;
}
}
visit = new boolean[n + 1];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (num[n1][n2] != -1 || num[n2][n1] != -1) {
int b_min = Math.min(b, num[n1][n2]);
num[n1][n2] = b_min;
num[n2][n1] = b_min;
} else {
num[n1][n2] = b;
num[n2][n1] = b;
}
}
solution(1);
System.out.println(min);
}
private static void solution(int level) {
if (level == n) {
min = Math.min(min, sum);
return;
}
for (int i = level; i < level+1; i++) {
for (int j = 1; j < n + 1; j++) {
if (num[i][j] != -1 && !visit[i] && !visit[j]) {
sum += num[i][j];
visit[i] = true;
solution(j);
sum -= num[i][j];
visit[i] = false;
}
}
}
}
}
문제 자체는 쉬웠다.... 다만 다익스트라 알고리즘이라서 좀 애먹었다
먼저 필자는 당연히 백트래킹을 이용해 풀려고 시도했다.
테스트 코드는 다 맞았고 제출했는데
오잉??? 메모리초과가 뜨는것이다....
N이 50000개 까지 입력되서 최악의 경우의수가 나오는듯 하다... 너무 비효율적이다...
저번에 이런 문제 풀때 백트래킹으로 잘 풀었는데... 아쉽다 ㅜㅜㅜㅜ 열심히 했는데
하지만 필자는 다익스트라 알고리즘을 전혀 모르는 상태! 그래서 구글링을 좀 하면서
내껄로 만들었다.
풀이
6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4
입력값은 다음과 같다.
static class Node implements Comparable<Node> {
int index;
int cost;
public Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.cost, other.cost);
}
}
일단은 먼저 Node 객체를 만들었다. compareTo를 사용하는 이유는 아래와 같다!
즉 이렇다!! 우선순위큐를 사실상 처음으로 사용해서 어려웠다....
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());
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 c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
// Run Dijkstra's algorithm
dijkstra(1);
// Output the shortest path from 1 to n
System.out.println("Shortest path cost: " + dist[n]);
// Print the shortest path
System.out.print("Path: ");
printPath(1, n);
}
그 후 입력을 받는다. List<List<Node>> 는 먼저 N을 전체적으로 리셋후 그 N들에 대한 Node의 갯수를 정하기 위함이다!
dijkstra(1);
그 후 이 메서드를 실행한다. 참고로
printPath(1, n);
이건 무시해도 된다. 필자가 공부좀 할려고 최소 노드 경로수를 구한것이다.
static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
dist = new int[n + 1];
predecessor = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(predecessor, -1);
dist[start] = 0;
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int currentNode = current.index;
int currentCost = current.cost;
if (currentCost > dist[currentNode]) continue;
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
}
}
여기가 핵심 코드이다. 차근차근 보자.
PriorityQueue<Node> pq = new PriorityQueue<>();
dist = new int[n + 1];
predecessor = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(predecessor, -1);
dist[start] = 0;
pq.offer(new Node(start, 0));
일단 이 부분에서 우선순위큐를 선언하고 dist 배열도 선언을 한다. (predecessor은 무시!)
그 다음 dist 배열에 최대 수로 초기화를 한다. 이렇게 하는 이유는 거리마다 최소 비용을 구하기 위함이다.
1부터 시작하므로
dist[start]=0 이라고 선언한뒤 큐에 넣는다.
0으로 한 이유는 1에서 1로 가는거는 0이기 때문이다.
while (!pq.isEmpty()) {
Node current = pq.poll();
int currentNode = current.index;
int currentCost = current.cost;
if (currentCost > dist[currentNode]) continue;
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
}
여기가 엄청 중요한 코드이다.
Node current = pq.poll();
int currentNode = current.index;
int currentCost = current.cost;
일단 아까전에 넣은 index와 cost를 불러온다 각각 1 하고 0이다.
if (currentCost > dist[currentNode]) continue;
그 후 if 문에서 currentCost는 0 dist[1] 은 0 즉 if 문이 실행안된다.
이것을 설정한 이유는 만약 1 - 2 - 4 까지 가는 비용이 2라고 생각해보자 그리고 dist[4]가 0일떄...
이거는 굳이 실행안하고 다음 단계로 가도 된다. 왜냐하면 최소 비용을 구하는 거기 때문에 불필요한 가짓수를 제거하는것이 좋기 때문이다.
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
그 후 graph.get(1) 을 해서 해당 Node를 불러온다. 이때 입력한 2 1 1 그리고 4 1 4 가 불러오게 되는데
즉 2 1, 4 4 이다!! (인접노드, 비용) 왜냐하면 입력할때 양방향으로 설정했기 때문!!
그러면 (2,1) 부터 보자!
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
newCost는 0 + 1 즉 2 이다!!
if 문에 들어오면 2 < 2143....... 이다 즉 통과가 된다.
참고로 이 if문을 설정한 이유는 위에서 설명한 것처럼 최소 비용을 알아서 걸러내기 위함이다.
그리고 dist[2] = 1이 되고 (predecessor은 무시!)
큐에 (2,1) 가 넣어지게 된다.
그럼 4도 동일하게 (4, 4) 가 넣어지게 된다. dist[4] = 4가 된채로!
그럼 다음 다시
Node current = pq.poll();
int currentNode = current.index;
int currentCost = current.cost;
일로 오게 된다. 우선순위 큐 즉 앞서 compareto에서 비용이 가장 낮은것을 우선으로 설정했기 때문에 (2,1) 이 넘어온다.
if (currentCost > dist[currentNode]) continue;
그럼 (2,1) if 문에 따라서 1 > 1 즉 성립이 안되기 때문에 아래로 간다.
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
2랑 인접한 노드를 앞서 입력한거에서 보면 (2,4,0) (3,2,6) (2,1,1) 이다. 정리를 해보면 (4,0) (3,6) (1,1) 이다.
( 4,0 ) 부터 보면 newCost = 1 + 0 즉 1이다.
if문에서 1 < 4 이기 때문에 당연히 들어오고 큐에 (4,1) 이 된채로 저장이 된다.
이때 dist[4]=4 에서 1로 변경이 된다!
(1,1) 을 보면 newCost= 1 + 1 이다.
하지만 if문에서 1 < 0 이기 때문에 성립이 안된다.
(3,6) 을 보면 newCost= 1 +6 즉 7 이다.
if 문에서 7 < 2143.... 이기 때문에 성립이 되고 (3,7) 은 큐에 저장이 된다.
자 그럼 지금 큐에 (4,1) (4,4) (3,6) 이 있다. 여기서 최소 비용을 우선적으로 하므로 (4,4) 가 먼저 있었지만 (4,1) 이 먼저 실행된다.
if (currentCost > dist[currentNode]) continue;
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
그럼 또 여기서
첫번째 if 문 1>1 성립 안됨... 그럼 아래로 들어간다.
자 그럼 4랑 인접된게 (4,5,3) (3,4,4) (4,1,4) 인데 정리를 하면 (5,3) (3,4) (1,4) 이다.
(5,3)은 newCost가 1 + 3 즉 4이고
if문에서 4 < 2143..... 성립이 된채로 들어와서 (5,4)가 된채로 큐에 저장이 된다.
(3,4)는 newCost가 1 + 4 즉 5이다.
if문에서 5 < 7 즉 성립이 된다. 그럼 dist[3]=5 로 바뀌고 (3,5) 가 된채로 큐에 저장!!
(1,4)는 newCost가 1 + 4 즉 5이다.
하지만 if문에서 5 < 0 이기 때문에 성립 XXXX
자 그럼 또 큐에서 현재 (4,4) (5,4) (3,4) 가 있다!!!
(4,4) 부터 보자
if (currentCost > dist[currentNode]) continue;
4,4 는 여기서부터 성립이 되서 패스당한다. 왜냐하면 현재 dist[4]=1 이기 때문이다 즉 4> 1 continue로 가면서 인접요소들을 넣지 못한다.
그럼 5,4 는???
if (currentCost > dist[currentNode]) continue;
일단 여기 성립되고
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
일로 온다!
즉 여기서 5랑 인접요소인 (4,5,3) (5,6,1) 이 있는데 정리를 하면 (4,3) (6,1) 이다 즉 계속 이런식으로 하면 정답이 나온다!!!
전체코드
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Graph5972 {
static class Node implements Comparable<Node> {
int index;
int cost;
public Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.cost, other.cost);
}
}
static int n, m;
static List<List<Node>> graph;
static int[] dist;
static int[] predecessor;
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());
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 c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
// Run Dijkstra's algorithm
dijkstra(1);
// Output the shortest path from 1 to n
System.out.println("Shortest path cost: " + dist[n]);
// Print the shortest path
System.out.print("Path: ");
printPath(1, n);
}
static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
dist = new int[n + 1];
predecessor = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(predecessor, -1);
dist[start] = 0;
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int currentNode = current.index;
int currentCost = current.cost;
if (currentCost > dist[currentNode]) continue;
for (Node neighbor : graph.get(currentNode)) {
int newCost = currentCost + neighbor.cost;
if (newCost < dist[neighbor.index]) {
dist[neighbor.index] = newCost;
predecessor[neighbor.index] = currentNode;
pq.offer(new Node(neighbor.index, newCost));
}
}
}
}
static void printPath(int start, int end) {
if (start == end) {
System.out.print(start + " ");
return;
}
if (predecessor[end] == -1) {
System.out.println("No path exists");
return;
}
printPath(start, predecessor[end]);
System.out.print(end + " ");
}
}
결과
느낀점
하 다익스트라 거의 처음 접한 알고리즘이라서 좀 오래걸렸다.... 발전해가보자.. 최근 프로젝트가 너무 많아서 코테를 많이 못하고 있다... 분발하자
728x90
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 영단어 암기는 괴로워 20920번 (🥈 실버3) (0) | 2024.09.15 |
|---|---|
| [백준] 탑 2493번 (🥇 골드5) (0) | 2024.08.23 |
| [백준] 리모컨 1107번 (🥇 골드5) (1) | 2024.07.03 |
| [백준] 회전초밥 2531번 (🥈실버1) (0) | 2024.06.06 |
| [백준] 지름길 1446번 (🥈실버1) (0) | 2024.06.06 |
'코딩테스트/백준' Related Articles
more
