알고리즘 - 백준 - 1753 - 최단경로

김성일·2024년 9월 2일
dijkstraheap그래프다익스트라메모리 초과백준알고리즘오버 플로우우선순위 큐유향그래프인접리스트인접행렬
4

알고리즘

목록 보기
5/23
post-thumbnail
post-custom-banner

문제 소개

  1. 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하시오. 단 모든 간선의 가중치는 양수
    ⇒ 제발 다익스트라(Dijkstra)로 풀어주세요
    ⇒ 출제자가 빌고있음
  2. 나이브한 다익스트라의 시간복잡도 = O(V^2)
    ⇒ 이 문제에서의 연산량 = 대략 20,000^2 = 400,000,000(4억)
    ⇒ 억단위면 시간복잡도 비빌만하다
    ⇒ 해당 방식 채택
    ⇒ 왜? 나이브하게 푸는 연습중. 아무튼 연습임.
  3. 서로 다른 두 정점 사이에 여러개의 간선이 존재할수도 있다
    ⇒ 그중에서 최소값을 쓰라는 뜻이겠죠?
    ⇒ 최단거리 구하는 문제잖아요…
    ⇒ 그래프에는 가중치의 최소값만 남겨두자

다익스트라 소개

바퀴를 두번 발명하지 마라~

다익스트라만 구현하면 되는 특별할거 없는 문제라서

다익스트라 구현을 설명하는 자료는 레퍼런스로 대체하겠습니다.

https://blog.naver.com/ndb796/221234424646

그래도 요약하자면~

  1. 시작점을 방문처리하고
  2. 시작점에서 갈수있는 각 노드의 거리를 계산한다.
  3. 방문하지 않은 노드중 시작점과 가장 가까운 노드를 고른다.
  4. 해당 노드에서 갈수있는 여러개의 다음 노드가 아래와 같다면 최단 거리 갱신이 가능하다.
    (시작점에서 해당 노드까지의 거리+해당 노드에서 다음 노드까지의 거리) <<<시작점에서 다음노드까지의 거리

무한 반복

3번을 수행하기 위해서 전체 배열을 순회하면 시간 복잡도는 O(N)이다.

4번을 수행하기 위해서는 시간 복잡도는 O(N)이 걸린다.

총 시간 복잡도는 O(N^2)가 되는데 여기서 더 최적화가 가능하다

💡

3번을 수행하기 위해서 minHeap을 사용하는 것이다.

그러면 가장 가까운 노드를 꺼내고 minHeap을 다시 업데이트 하는데 시간복잡도가 O(LogN)이다.

그러면 종합적으로 시간복잡도는 O(N*LogN)이 걸린다.

나이브한 다익스트라 - 인접행렬

오버플로우가 가로막다

도달 불가능하다는 의미로 INF = Integer.MAX_VALUE 사용함 ⇒ 오버플로우 발생

적당히 큰 값으로 INF를 수정함 ⇒ 샘플 테케에서 정상 작동

INF의 기준 = 가중치 최대값(10) * 간선의 최대개수(200,000) + 안전빵(1) ⇒ 도달 불가능

기준 못 찾겠다? ⇒ BruteForce로 테스트해서 찾으세요 ⇒ 이진탐색하면 더 빠르겠다 그쵸

메모리가 터져버리다

그래프를 인접행렬로 구현해봤다 ⇒ 메모리가 터졌다 ⇒ 그럴리가 256메가라고

메모리 계산 시작

  1. 정점이 최대 20,000개니까
  2. 인접행렬은 최대 20,000*20,000이니까 4억개의 셀을 가지고 있고.
  3. 각 셀은 int타입이니까 4byte를 가지고 있으므로 총 16억바이트 ⇒ 메모리 사용량 1.6기가
  4. 인접행렬은 못 쓰겠다 ⇒ 테이블이 Sparse하다 ⇒ 간선개수 300,000개에서 감이 올만하긴함.
  5. 간선의 최대값은 (20,000)*(20,000-1)/2니까…
  6. 메모리 때문에 인접행렬 못 쓴다 ⇒ 인접리스트 사용 ⇒ 테이블이 Dense하지 않다 ⇒ 테이블이 Sparse하다
package lecture.d0902;

import java.io.*;
import java.util.*;

public class BOJ_G4_1753_최단경로 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	static int V;
	static int E;
	
	// 세팅
	static boolean[] visit;
	static int[] distance;
	static int[][] graph;
//	static int INF = Integer.MAX_VALUE;
	static int INF = 10*200_000+1;
			
	// 메소드
	static int getMinNode() {
		int min = INF;
		int node = 0;
		for (int i = 0; i < V; i++) {
			if( (distance[i]<min) && (visit[i]==false) ) {
				min = distance[i];
				node = i;
			}
		}
		return node;
	}
	
	//// 다익스트라
	static void dijkstra(int start) {
		visit = new boolean [V];
		visit[start-1] = true;
		distance = graph[start-1];
		distance[start-1] = 0;
		
		for (int i = 0; i < V; i++) {
			int currentNode = getMinNode();
			visit[currentNode] = true;
			for (int node = 0; node < V; node++) {
				if(visit[node]==false) { // 방문이면 이미 최소화 루트를 통해서 결정된 값이기때문에 최소값임. 굳이 갱신할필요가 없음. 갱신하는 로직에 포함시켜도 됨. 어차피 더 작은 값이 안 붙어서 갱신안됨.
					if(distance[currentNode] + graph[currentNode][node] < distance[node]) {
						distance[node] = distance[currentNode] + graph[currentNode][node];
					}
				}
			}
		}
		
	}
	
	
	// 메인
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		V = Integer.parseInt(tokens.nextToken());
		E = Integer.parseInt(tokens.nextToken());
		int start = Integer.parseInt(input.readLine());
		graph = new int[V][V];
		for (int i = 0; i < graph.length; i++) {
			Arrays.fill(graph[i], INF);
		}
//		System.out.println(Arrays.deepToString(graph));
//		System.out.println("=============");
		for (int i = 0; i < E; i++) {
			tokens = new StringTokenizer(input.readLine());
			int row = Integer.parseInt(tokens.nextToken())-1;	// -1 해서 그래프에 맞게 넣음.
			int col = Integer.parseInt(tokens.nextToken())-1;	// -1
			int weight = Integer.parseInt(tokens.nextToken());
			int value = graph[row][col];
			graph[row][col] = Math.min(value, weight); // 최소값 업데이트

		}
//		for (int i = 0; i < graph.length; i++) {
//			System.out.println(Arrays.toString(graph[i]));
//		}
		
		
		// 세팅
//		visit = new boolean[V];
//		distance = new int[V];
//		Arrays.fill(distance, INF);
		// 작업
		dijkstra(start);
		// 출력
		for (int i = 0; i < V; i++) {
			if(distance[i]==INF) {
				output.append("INF").append("\n");
			} else {
				output.append(distance[i]).append("\n");
			}
		}
		System.out.println(output);

	}

}

나이브한 다익스트라 - 인접리스트

인접 행렬을 인접 리스트로 바꾼다 ⇒ 관련 로직 수정 ⇒ 성공 ⇒ 나이브로도 충분

바뀐 부분

최소 가중치 간선 갱신 로직과 코드

dijkstra 돌때 참조하는 코드

package lecture.d0902;
// 인접 리스트로...
import java.io.*;
import java.util.*;

public class BOJ_G4_1753_최단경로2 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	static int V;
	static int E;
	
	// 세팅
	static boolean[] visit;
	static int[] distance;
	static ArrayList<int[]>[] graph; // int[]을 담는 ArrayList의 배열 ㅋㅋ..
	static int INF = 10*200_000+1;
			
	// 메소드
	static int getMinNode() {
		int min = INF;
		int node = 0;
		for (int i = 0; i < V; i++) {
			if( (distance[i]<min) && (visit[i]==false) ) {
				min = distance[i];
				node = i;
			}
		}
		return node;
	}
	
	//// 다익스트라
	static void dijkstra(int start) {
		// 부품 초기화 1
		visit = new boolean [V];
		visit[start-1] = true;
		distance = new int [V];
		Arrays.fill(distance, INF);
		// 부품 초기화 2
		distance[start-1] = 0;
		for (int i = 0; i < graph[start-1].size(); i++) { // 어레이 리스트 순회
			int node = graph[start-1].get(i)[0];
			int weight = graph[start-1].get(i)[1];
			distance[node] = weight;
		}
		
		for (int i = 0; i < V; i++) {
			int currentNode = getMinNode();
			visit[currentNode] = true;
			for (int node = 0; node < graph[currentNode].size(); node++) {
				int nextNode = graph[currentNode].get(node)[0];
				int nextWeight = graph[currentNode].get(node)[1];
				if(visit[nextNode] == false) { // 방문이면 이미 최소화 루트를 통해서 결정된 값이기때문에 최소값임. 굳이 갱신할필요가 없음. 갱신하는 로직에 포함시켜도 됨. 어차피 더 작은 값이 안 붙어서 갱신안됨.
					if(distance[currentNode] + nextWeight < distance[nextNode]) {
						distance[nextNode] = distance[currentNode] + nextWeight;
					}
				}
			}
		}
	}
	
	
	// 메인
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		V = Integer.parseInt(tokens.nextToken());
		E = Integer.parseInt(tokens.nextToken());
		int start = Integer.parseInt(input.readLine());
		graph = new ArrayList[V];
		for (int i = 0; i < V; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < E; i++) {
			tokens = new StringTokenizer(input.readLine());
			int row = Integer.parseInt(tokens.nextToken())-1;	// -1 해서 그래프에 맞게 넣음.
			int col = Integer.parseInt(tokens.nextToken())-1;	// -1
			int weight = Integer.parseInt(tokens.nextToken());
			// 인접리스트 생성 + 업데이트
			boolean isAlready = false;
			for (int j = 0; j < graph[row].size(); j++) {
				int alreadyNode = graph[row].get(j)[0];
				int alreadyWeight = graph[row].get(j)[1];
				if(alreadyNode==col) { // 같은 노드를 잇는 간선이 기존에 있음 => 최소값만 남김.
					graph[row].get(j)[1] =  Math.min(weight, alreadyWeight);
					isAlready = true;
					break;
				}
			}
			if(isAlready==false) { // 기존에 없다고? 추가해~
				graph[row].add(new int[] {col,weight});
			}
		}
//		for (int i = 0; i < graph.length; i++) {
//			System.out.println(Arrays.toString(graph[i]));
//		}
		
		
		// 세팅

		// 작업
		dijkstra(start);
		// 출력
		for (int i = 0; i < V; i++) {
			if(distance[i]==INF) {
				output.append("INF").append("\n");
			} else {
				output.append(distance[i]).append("\n");
			}
		}
		System.out.println(output);

	}

}

나이스한 다익스트라 - minHeap을 사용

다음 포스트에서 이어짐
https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1753-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9CVer2-JAVA

간선이 풀로 있는 완전그래프면 방문을 모두 끝마쳤을때 탈출하는게 바람직해보임

minHeap을 안쓰는 나이브한 방법에서는 최소값을 유지해줘야 했지만,
minHeap을 쓰면 어차피 최소값인 간선만 타게 되니까 그래프를 표현할때 최소값을 쓸 필요가 없다.

profile
김성일
better을 통해 best로
이전 포스트

알고리즘 - 백준 - 1753 - 최단경로(Ver2) - JAVA

다음 포스트

알고리즘 - 백준 - 2512 - 예산 - JAVA

post-custom-banner

1개의 댓글

comment-user-thumbnail
인귤
2024년 9월 4일

정성스러운 포스팅 잘보고 가용!

이제 날씨가 많이 풀렸는데 따뜻한 봄햇살을 맞으시면서 오늘도 내일도 매일매일 행복한 하루를 보내시길 바래용!

가끔씩 시간 나시면 제 블로그도 한번씩 들려주시면 감사하겠습니다 ^^ ♥

자주 놀러올께욧!

답글 달기