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--해주고 이전에 들어온 값을 제거한 후에 최단경로가 변경된 노드의 값을 리스트 배열에 넣어준다. 그리고 모든 알고리즘이 종료된 후에는 최단 경로에 해당하는 노드들의 연결이 배열 리스트에 저장이 되어 있게된다.

posted by 여성게
:

1. 그래프 이론 - 섬의 개수 (백준 4963번)






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
package _317324;
 
import java.util.Scanner;
 
public class Baekjoon4963NumberofIsland {
    static int count;
    static int[] dx= {-1,-1,0,1,1,1,0,-1};
    static int[] dy= {0,1,1,1,0,-1,-1,-1};
    static int[][] map=new int[50][50];
    static int height;
    static int weight;
    static void countIsland(int h,int w) {
        int nx=0;
        int ny=0;
        map[h][w]=2;
        for(int i=0;i<8;i++) {
            nx=w+dx[i];
            ny=h+dy[i];
            
            if(nx>=weight || nx<|| ny>=height || ny<0) {
                continue;
            }
            if(map[ny][nx]==1) {
                countIsland(ny, nx);
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        StringBuffer sb=new StringBuffer();
        while(true) {
            weight=sc.nextInt();
            height=sc.nextInt();
            if(weight==&& height==0break;
            
            for(int i=0;i<50;i++) {
                for(int j=0;j<50;j++) {
                    map[i][j]=0;
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    map[i][j]=sc.nextInt();
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    if(map[i][j]==1) {
                        countIsland(i, j);
                        count++;
                    }
                }
            }
            sb.append(count+"\n");
            count=0;
        }
        System.out.println(sb);
    }
 
}
 
cs



문제의 풀이는 배열 안에 섬의 표시가 1로 표시가 되고 가로, 세로 및 대각선이 연결된 섬으로 인식이 되는 것이다. 1행부터 열을 탐색하여 1이 나오는 배열의 인덱스를 찾게 되면 그 배열의 좌표를 기준으로 countIsland 메소드를 호출하게 된다. 메소드 안에 좌표가 전달되면 전역 변수로 선언한 dx,dy 배열을 이용하여 연결된 섬을 찾게 된다. 좌표는 시작으로 부터 왼쪽, 왼쪽대각선위, 위, 오른쪽 대각선위, 오른쪽, 오른쪽 대각선 아래, 아래, 왼쪽대각선 아래를 뜻하게 된다. 그렇게 8방을 반복문으로 하나하나 따져봐서 인접한 1을 찾게 되는 것이다. 이 반복문 안에 첫번째 조건문이 뜻하는 바는 처음에 입력값으로 선언된 높이와 넓이의 직사각형을 벗어나는지를 따져보는 것이다. 만약 직사각형의 범위를 벗어나지 않으면서 팔방의 위치에 1이 존재한다면? 그 좌표를 방문했다는 표시로 모두 2로 배열의 값을 변경해준다.(그러면 더 이상 이섬은 탐색하지 않는다.)그리고 이섬은 연결된 섬으로 간주하고 그 섬의 좌표를 기준으로 countIsland 메소드를 다시 호출하게 된다. 즉, 그래프의 깊이우선 탐색을 실행하여 탐색하다가 더 이상 연결된 섬이 없을 때는 백트랙킹으로 이전의 좌표로 돌아가 이 좌표를 기준으로 다시 깊이 우선탐색을 실행하는 것이다. 그러다가 더 이상 탐색할 곳이 없게되면 함수를 종료하게 된다.(이 과정까지가 처음 발견된 1의 좌표를 기준으로 연결된 섬을 모두 탐색하고 난 후 종료하는 과정이다.) 

posted by 여성게
:

이 문제같은 경우는 최소신장트리를 구하는 알고리즘이다. 최소신장트리를 구하는 알고리즘은 크게 프림알고리즘과 크루스칼알고리즘 두가지가 있다. 여기서 조금더 구현하기가 수월한 프림알고리즘을 이용하여 최소신장트리를 구현할것이다.





1. 최소신장 트리란?



최소 신장트리란 주어진 그래프에서 모든 정점을 연결하며 그 비용이 최소인 간선만 연결된 트리를 말한다.




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
package graph;
 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
class AdjVertex implements Comparable<AdjVertex> {
    int adjVertex;
    int weight;
    public AdjVertex(int adjVertex,int weight) {
        // TODO Auto-generated constructor stub
        this.adjVertex=adjVertex;
        this.weight=weight;
    }
    @Override
    public int compareTo(AdjVertex 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 Baekjun1197MinSpanningTree {
    
    static ArrayList<AdjVertex>[] vertexList;
    static boolean visited[];
    static int result;
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int V=sc.nextInt();
        int E=sc.nextInt();
        
        vertexList=new ArrayList[V+1];
        visited=new boolean[V+1];
        
        //인접리스트 초기화
        for(int i=1;i<V+1;i++) {
            vertexList[i]=new ArrayList<AdjVertex>();
        }
        for(int i=0;i<E;i++) {
            int start=sc.nextInt();
            int end=sc.nextInt();
            int weight=sc.nextInt();
            AdjVertex av=new AdjVertex(end, weight);
            AdjVertex av2=new AdjVertex(start, weight);
            vertexList[start].add(av);
            vertexList[end].add(av2);
        }
        //최소값을 빼주기 위한 우선순위 큐
        PriorityQueue<AdjVertex> pq=new PriorityQueue<AdjVertex>();
        visited[1]=true;
        Iterator<AdjVertex> it=vertexList[1].iterator();
        while(it.hasNext()) {
            pq.offer(it.next());
        }
        int count=0;
        while(!pq.isEmpty()) {
            AdjVertex pollVertex=pq.poll();
            int v=pollVertex.getAdjVertex();
            if(visited[v]==truecontinue;
            int w=pollVertex.getWeight();
            result+=w;
            visited[v]=true;
            count++;
            if(count==V+1break;
            Iterator<AdjVertex> it2=vertexList[v].iterator();
            while(it2.hasNext()) {
                pq.add(it2.next());
            }
        }
        System.out.println(result);
    }
}
 
cs


다익스트라 알고리즘과 비슷한 로직을 가집니다. 다만 큐에서 최소값을 빼주며 방문한 정점들을 체크를 해주어서 이미 체크된 정점 같은 경우는 결과값에 포함시키지않는다. 

posted by 여성게
:

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






백준-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배열에 들어가기때문에 단순히 앞의 최단경로 문제 코드에서 출력부분만 수정해주면 된다. 다익스트라 알고리즘 구동방식은 최단거리문제 설명에 그림으로 설명되어있다.

posted by 여성게
:


백준-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와 비슷하게 큐를 이용하지만 그냥 큐가 아니라 우선순위 큐를 이용하여 구현한다. 

posted by 여성게
:

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



posted by 여성게
:


그래프 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]==&& vertexList[j].visited==falsereturn 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]==&& vertexList[j].visited==falsereturn 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]==&& vertexList[j].visited==falsereturn 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


posted by 여성게
: