패스트캠퍼스 챌린지 31일차

최단 경로 (Shortest Path)

 

최단 거리란?

 - 그래프의 시작점에서 다른 지점 까지의 최단 거리

 EX) 네비게이션 

 

1. BFS

 - 간선의 가중치 모두 1

 - 시작점은 한 정점

 - 도착점은 모든 정점

 - 시간 복잡도 O(V+E)

 

 

2. Dijkstra

 - 간선의 가중치 모두 0 이상

 - 시작점은 한 정점

 - 도착점은 모든 정점

 - 시간 복잡도 O(ElogV)

 

필요한 정보

 - dist[i] : 시작점에서 i번 정점까지 가능한 최단 거리 => 다익스트라 알고리즘이 한번 돌떄마다 배열이 채워짐

 - 자료구조 D : 시작점에서 v까지 d만에 갈 수 있음을 확인

 

 구현 순서

  1. dist 배열 초기화, dist[i] = o if i == S , else

  2. D에 (S,0)을 추가한다

  3. min(v,d), D에서 가장 작은 d를 갖는 자료 (v,d)를 뽑는다.

  4. dist[v] < d

   => v까지의 최단 거리보다 d가 크다면, 이미 가치가 없는 정보이므로 폐기한다.

  5. v,d를 통해 새로운 정보를 D에 추가

 

 

다익스트라는 음수 간선이 있으면 안된다.

 

 

최소비용 구하기 (BOJ 1916)

 - 최단거리 특성 : 같은 정점을 두 번 방문할 이유가 없다. 따라서 정답은 버스비 (10만) * 정점 수(1천) = 1억 

   => Integer 로 충분 (100억 이하) 

 

 

구현

	static int N, M, start, end;
	static int[] dist;
	static ArrayList<Edge>[] edges;
    
      static void dijkstra(int start) {
        // 모든 정점까지에 대한 거리를 무한대로 초기화 해주기.
        // ※주의사항※
        // 문제의 정답으로 가능한 거리의 최댓값보다 큰 값임을 보장해야 한다.
        for (int i = 1; i <= N; i++) dist[i] = Integer.MAX_VALUE;

        // 최소 힙 생성
        PriorityQueue<Info> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
        // 다른 방법) PriorityQueue<Info> pq = new PriorityQueue<>((o1, o2) -> o1.dist - o2.dist);

        // 시작점에 대한 정보(Information)을 기록에 추가하고, 거리 배열(dist)에 갱신해준다.
        pq.add(new Info(start, 0));
        dist[start] = 0;

        // 거리 정보들이 모두 소진될 때까지 거리 갱신을 반복한다.
        while (!pq.isEmpty()) {
            Info info = pq.poll();
            
            // 꺼낸 정보가 최신 정보랑 다르면, 의미없이 낡은 정보이므로 폐기한다.
            if (dist[info.idx] != info.dist) continue;

            // 연결된 모든 간선들을 통해서 다른 정점들에 대한 정보를 갱신해준다.
            for (Edge e : edges[info.idx]) {
                if (dist[info.idx] + e.weight >= dist[e.to]) continue;

                // e.to 까지 갈 수 있는 더 짧은 거리를 찾았다면 이에 대한 정보를 갱신하고 PQ에 기록해준다.
                dist[e.to] = dist[info.idx] + e.weight;
                pq.add(new Info(e.to, dist[e.to]));
            }
        }
    }

    static void pro() {
        dijkstra(start);
        System.out.print(dist[end]);
    }

 

31일차 인증

 

 

 

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]