알고리즘&자료구조/그래프&다익스트라 2018. 3. 31. 00:58

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

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




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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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());
            }
        }
    }
 
}
 
cs


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

저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
위상정렬(백준 2252번 줄세우기)  (0) 2018.02.20
posted by 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 22. 10:38

최소비용구하기-다익스트라알고리즘(백준 1916번)

이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다.





백준-1916번 최소비용 구하기



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package graph;
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;

class AdjVertex2 implements Comparable<AdjVertex2> {
    int adjVertex;
    int weight;
    public AdjVertex2(int adjVertex,int weight) {
        // TODO Auto-generated constructor stub
        this.adjVertex=adjVertex;
        this.weight=weight;
    }
    @Override
    public int compareTo(AdjVertex2 o) {
        // TODO Auto-generated method stub
        if(this.weight>o.getWeight()) return 1;
        else if(this.weight==o.getWeight()) return 0;
        else return -1;
    }
    public int getAdjVertex() {
        return adjVertex;
    }
    public void setAdjVertex(int adjVertex) {
        this.adjVertex = adjVertex;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
public class Baekjun1916UpdateCode {
    static ArrayList<AdjVertex2>[] vertexList;
    static int[] distance;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        PriorityQueue<AdjVertex2> pq=new PriorityQueue<AdjVertex2>();
        
        int V=sc.nextInt();
        int E=sc.nextInt();
        
        vertexList=new ArrayList[V+1];
        distance=new int[V+1];
        for(int i=1;i<V+1;i++) {
            vertexList[i]=new ArrayList<AdjVertex2>();
            distance[i]=Integer.MAX_VALUE;
        }
        
        for(int i=0;i<E;i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            int w=sc.nextInt();
            AdjVertex2 adVertex=new AdjVertex2(v,w);
            vertexList[u].add(adVertex);
        }
        int K=sc.nextInt();
        int M=sc.nextInt();
        distance[K]=0;
        pq.offer(new AdjVertex2(K,distance[K]));
        while(!pq.isEmpty()) {
            AdjVertex2 vertexInfo=pq.poll();
            int index=vertexInfo.getAdjVertex();
            int weight=vertexInfo.getWeight();
            Iterator<AdjVertex2> it=vertexList[index].iterator();
            while(it.hasNext()) {
                AdjVertex2 adVertex=it.next();
                int index1=adVertex.getAdjVertex();
                int weight1=adVertex.getWeight();
                    
                if(distance[index1]>distance[index]+weight1) {
                distance[index1]=distance[index]+weight1;
                pq.offer(adVertex);
                }
            }
        }
        System.out.println(distance[M]);
    }
}
 
cs


출발도시에서 도착도시까지의 최소비용을 구하는 것이므로 출력부분을 도착도시의 거리를 출력해주면된다. 왜냐하면 다익스트라 알고리즘은 시작정점으로부터 모든 정점까지의 최소비용들이 모두 distance배열에 들어가기때문에 단순히 앞의 최단경로 문제 코드에서 출력부분만 수정해주면 된다. 다익스트라 알고리즘 구동방식은 최단거리문제 설명에 그림으로 설명되어있다.

저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
위상정렬(백준 2252번 줄세우기)  (0) 2018.02.20
그래프 DFS 와 BFS  (0) 2018.02.20
posted by 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 22. 10:31

최단거리-다익스트라알고리즘(백준 1753번 문제)


백준-1753번 최단거리


시작정점으로부터 모든 정점까지의 최단거리를 구하는 문제이다. 이 문제는 BFS와 비슷한 다익스트라 알고리즘으로 풀 수 있는 문제이다. 다익스트라 알고리즘은 방향이있는 가중치 그래프에서 어떤 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘이다.(음수간선을 포함하는 그래프는 다익스트라 알고리즘으로 풀 수 없다.)




위의 그림과 같은 과정으로 다익스트라 알고리즘이 구동됩니다. ( 코드에서는 방문여부에 관한 check배열은 선언하지 않았음 굳이 없어도 돌아감)




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
/*
4 5
1 2 1
4 2 -2
3 2 -8
3 4 -3
4 1 -88
*/
class AdjVertex1 implements Comparable<AdjVertex1> {
    int adjVertex;
    int weight;
    public AdjVertex1(int adjVertex,int weight) {
        // TODO Auto-generated constructor stub
        this.adjVertex=adjVertex;
        this.weight=weight;
    }
//우선순위 큐에 삽입될때 정렬할 기준을 가준치로 정해주는 것이다.
    @Override
    public int compareTo(AdjVertex1 o) {
        // TODO Auto-generated method stub
        if(this.weight>o.getWeight()) return 1;
        else if(this.weight==o.getWeight()) return 0;
        else return -1;
    }
    public int getAdjVertex() {
        return adjVertex;
    }
    public void setAdjVertex(int adjVertex) {
        this.adjVertex = adjVertex;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
public class Baekjun1753UpdateCode {
    static ArrayList<AdjVertex1>[] vertexList;
    static int[] distance;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        PriorityQueue<AdjVertex1> pq=new PriorityQueue<AdjVertex1>();
        
        int V=sc.nextInt();
        int E=sc.nextInt();
        int K=sc.nextInt();
        
        vertexList=new ArrayList[V+1];
        distance=new int[V+1];
//인접리스트 초기화 및 거리 배열 초기화(거리배열은 무한대값 개념으로 초기화해준다.)
        for(int i=1;i<V+1;i++) {
            vertexList[i]=new ArrayList<AdjVertex1>();
            distance[i]=Integer.MAX_VALUE;
        }
//시작정점의 거리는 0으로 초기화해준다.(자기자신으로 들어가는 거리는 0임으로)
        distance[K]=0;
        for(int i=0;i<E;i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            int w=sc.nextInt();
            AdjVertex1 adVertex=new AdjVertex1(v,w);
            vertexList[u].add(adVertex);
        }
//시작정점 K에서 자기자신 K로 들어가는 거리는 0이다. 라는 객체를 우선순위큐에 삽입
        pq.offer(new AdjVertex1(K,distance[K]));
        while(!pq.isEmpty()) {
//가중치가 가장 작은 정점과 가중치 쌍을 poll해준다.(기준정점이 삭제된 이후의 큐는 방문하지 않은 정점중
//가중치가 가장 작은 정점을 poll한다.)
            AdjVertex1 vertexInfo=pq.poll();
            int index=vertexInfo.getAdjVertex();
            int weight=vertexInfo.getWeight();
//우선순위 큐에서 삭제한 정점의 인접한 정점들을 구한다.
            Iterator<AdjVertex1> it=vertexList[index].iterator();
            while(it.hasNext()) {
                AdjVertex1 adVertex=it.next();
                int index1=adVertex.getAdjVertex();
                int weight1=adVertex.getWeight();
//거리가 무한대이거나 OR 이전에 갱신된 거리보다 지금 방문한 거리가 작다면 거리를 다시 갱신해준다.
                if(distance[index1]>distance[index]+weight1) { distance[index1]=distance[index]+weight1; pq.offer(adVertex); } } } for(int i=1;i<V+1;i++) { if(distance[i]<Integer.MAX_VALUE) System.out.println(distance[i]); else System.out.println("INF"); } } }


BFS와 비슷하게 큐를 이용하지만 그냥 큐가 아니라 우선순위 큐를 이용하여 구현한다. 

저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
위상정렬(백준 2252번 줄세우기)  (0) 2018.02.20
그래프 DFS 와 BFS  (0) 2018.02.20
posted by 여성게
:

티스토리툴바