그래프 다익스트라 - 네트워크 복구(백준 2211번)

1. 그래프 다익스트라 - 네트워크 복구(백준 2211번)

---

---

2. 다익스트라 알고리즘을 이용한 문제풀이

---

package _317324;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Baekjoon2211NetworkRepairDijkstra {
    static ArrayList<String>[] vertextList;
    static ArrayList<Integer>[] result;
    static int[] distance;
    static int count=0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        
        result=new ArrayList[n+1];
        vertextList=new ArrayList[n+1];
        distance=new int[n+1];
        
        PriorityQueue<String> pq=new PriorityQueue<>(new Comparator<String>() {
 
            @Override
            public int compare(String o1, String o2) {
                // TODO Auto-generated method stub
                String[] strArr1=o1.split(" ");
                String[] strArr2=o2.split(" ");
                
                String a=distance[Integer.parseInt(strArr1[0])]+"";
                String b=distance[Integer.parseInt(strArr2[0])]+"";
                return a.compareTo(b);
            }
        });
        for(int i=1;i<n+1;i++) {
            result[i]=new ArrayList<Integer>();
            vertextList[i]=new ArrayList<String>();
            distance[i]=Integer.MAX_VALUE;
        }
        distance[1]=0;
        for(int i=0;i<m;i++) {
            int from=sc.nextInt();
            int to=sc.nextInt();
            int weight=sc.nextInt();
            vertextList[from].add(to+" "+weight);
            vertextList[to].add(from+" "+weight);
        }
        pq.offer(1+" "+distance[1]);
        
        while(!pq.isEmpty()) {
            String[] vertexInfo=pq.poll().split(" ");
            Iterator<String> it=vertextList[Integer.parseInt(vertexInfo[0])].iterator();
            while(it.hasNext()) {
                String adVertex=it.next();
                String[] adVertexArr=adVertex.split(" ");
                if(distance[Integer.parseInt(adVertexArr[0])]>distance[Integer.parseInt(vertexInfo[0])]
                        +Integer.parseInt(adVertexArr[1])) {
                    distance[Integer.parseInt(adVertexArr[0])]=distance[Integer.parseInt(vertexInfo[0])]
                            +Integer.parseInt(adVertexArr[1]);
                    count++;
                    for(int i=1;i<result.length;i++) {
                        Iterator<Integer> it1=result[i].iterator();
                        int index=0;
                        while(it1.hasNext()) {
                            if(it1.next()==Integer.parseInt(adVertexArr[0])) {
                                result[i].remove(index);
                                count--;
                                break;
                            }
                            index++;
                        }
                    }
                    result[Integer.parseInt(vertexInfo[0])].add(Integer.parseInt(adVertexArr[0]));
                    pq.offer(adVertex);
                }
            }
        }
        System.out.println(count);
        for(int i=1;i<result.length;i++) {
            Iterator it=result[i].iterator();
            while(it.hasNext()) {
                System.out.println(i+" "+it.next());
            }
        }
    }
 
}
 

다익스트라 알고리즘을 이용하여 최소 경로를 구하는 문제이다. 하지만 여기에서 최소경로만 구하는 것이 아니라 최소 경로에 해당하는 노드들의 연결까지 출력하는 문제이다.(최소 경로 값만 출력하면 쉬운문제이다. 앞에서 다루었던 최소경로,최소비용 문제를 참고하면 된다. 다익스트라 알고리즘 설명은 따로 하지 않는다.) 위의 코드는 조금은 비효율적인 코드라서 나중에 수정하기는 하겠지만, 이 코드를 설명하면 무한대 값으로 초기화되있는 노드들의 값을 최단 경로로 변경될때 마다 result라는 리스트 배열에 두 노드의 값을 넣어 준다. 하지만 값을 넣어주기 전에 이전에 같은 노드의 값이 들어와있는지 반복문을 통해 검사해 만약 이전에 이 노드 값이 들어오지 않았다면 그냥 result 리스트 배열에 값을 넣어주고 만약 이전에 같은 노드가 들어왔었다면 count--해주고 이전에 들어온 값을 제거한 후에 최단경로가 변경된 노드의 값을 리스트 배열에 넣어준다. 그리고 모든 알고리즘이 종료된 후에는 최단 경로에 해당하는 노드들의 연결이 배열 리스트에 저장이 되어 있게된다.