'알고리즘&자료구조'에 해당되는 글 19건

  1. 2018.02.22 :: 최단거리-다익스트라알고리즘(백준 1753번 문제)
  2. 2018.02.20 :: 위상정렬(백준 2252번 줄세우기)
  3. 2018.02.20 :: 그래프 DFS 와 BFS
알고리즘&자료구조/그래프&다익스트라 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 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 20. 00:37

위상정렬(백준 2252번 줄세우기)

1. 위상정렬

위상정렬의 조건

위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다.



진입차수를 이용한 위상정렬


1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.

(방향 그래프 완성)

2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)

3. indegree가 0인 일을 모두 찾아 큐에 넣는다

4. 큐에서 정점 하나를 꺼낸다.

(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)

5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.

6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.

7. 큐가 빌 때까지 4~6을 반복한다.





2.위의 위상정렬을 이용한 백준 2252번 줄세우기 문제)




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
package graph;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class TopologySort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        Queue<Integer> queue =new LinkedList<Integer>();
        int n=sc.nextInt();
        int m=sc.nextInt();
        LinkedList<Integer>[] vertexArr = new LinkedList[n];
        for(int i=0;i<n;i++) {
            vertexArr[i]=new LinkedList<Integer>();
        }
        int[] indegree=new int[n];
        for(int i=0;i<m;i++) {
            int v=sc.nextInt();
            int w=sc.nextInt();
            vertexArr[v-1].add(w-1);
            indegree[w-1]+=1;
        }
        for(int i=0;i<n;i++) {
            if(indegree[i]==0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int x=queue.poll();
            System.out.print(x+1+" ");
            Iterator<Integer> it=vertexArr[x].iterator();
            while(it.hasNext()) {
                int y=it.next();
                indegree[y]--;
                if(indegree[y]==0) {
                    queue.offer(y);
                }
            }
        }
    }
 
}
 
cs



저작자표시

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

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
그래프 DFS 와 BFS  (0) 2018.02.20
posted by 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 20. 00:26

그래프 DFS 와 BFS


그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색)


1. 시작전

그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다.





2.DFS(깊이우선탐색)



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
package graph;
 
import java.util.Stack;
 
public class DFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    public DFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DFS d=new DFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        //1번 정점부터 방문시작
        d.dfs(1);
    }
 
}//결과 : 1 2 4 3 5 6 7
 
cs


설명:  1번 정점부터 시작하므로 스택에 1번정점을 넣어준다. 그리고 스택에서 peek을 하여 1번정점을 꺼내어 1번정점에 대한 인접행렬의 행을 탐색하여 첫번째로 나오는 visited가 false인 연결정점(2번정점)을 visited=true로 바꿔주고 스택에 넣어준다. 그리고 다시 스택에서 peek을 하여 이전에 넣었던 2번정점을 읽어와 2번정점에 대한 인접행렬 행을 읽어 첫번째로 나오는 visited가 false인 연결정점(4번정점)을 visited=true로 바꿔 주고 스택에 넣어준다. 이런 과정을 진행하다가 막다른 지점이 나오면(4번정점) 그에 대한 인접행렬의 행에서 visited가 false 인접한 정점이 존재하지 않으므로 스택에서 pop해주어 백트래킹을 진행한다. 그러다 1번정점에서 다시 visited가 false 인접정점이 존재하므로 위의 과정을 반복하게 된다.




3.BFS(너비우선탐색)

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
package graph;
 
 
import java.util.LinkedList;
import java.util.Queue;
 
import graph.DFS.Vertex;
 
public class BFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Queue queue;
    public BFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        queue=new LinkedList();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BFS d=new BFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        d.bfs(1);
    }
 
}//결과: 1 2 3 4 5 6 7
 
cs


설명: 시작정점 1번을 방문후 큐에 삽입해준다. 그리고 큐에서 poll을 해서 1번정점을 빼주고 1번노드 다음레벨에 해당하는(인접하고있는) 정점들을 모두 방문 후 큐에 삽입해준다.(2번정점 3번정점) 그리고 큐에서 poll을 해서 2번정점을 빼주고 2번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(4번정점) 그다음 큐에서 poll을 해 3번 정점을 빼주고 3번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(5,6,7번정점).. 이과정을 반복해준다.




4. 백준 1260번 DFS와 BFS  



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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package graph;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
public class DFSBFS {
    class Vertex{
        public String label;
        public boolean visited;
        public Vertex(String label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=1000;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    private Queue queue;
    public DFSBFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
        queue=new LinkedList();
    }
    public void addVertex(String label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label+" ");
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        DFSBFS ma=new DFSBFS();
        int n=sc.nextInt();
        int m=sc.nextInt();
        int v=sc.nextInt();
        
        for(int i=0;i<n;i++) {
            ma.addVertex(i+1+"");
        }
        while(m!=0) {
            ma.addEdge(sc.nextInt()-1,sc.nextInt()-1);
            m--;
        }
        ma.dfs(v);
        ma.bfs(v);
    }
 
}
 
cs


저작자표시

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

그래프이론 - 섬의 개수(백준 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 여성게
:

티스토리툴바