# BFS 두 번 사용하여, 첫 번째에는 BFS를 통해 그룹화 시키고 두 번째에는 그룹화 된 배열을 가지고 BFS를 수행하며 최단거리를 구함

package bj;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p2146 {
	static int arr[][];
	static int graph[][];
	static int n;
	static int moveX[] = {0,1,0,-1};
	static int moveY[] = {-1,0,1,0};
	static boolean visit[][];
	static int cnt=1;
	static int rs=9999;
	static ArrayList<Point>[] arrList;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n][n];
		visit = new boolean[n][n];
		graph = new int[n][n];
		arrList = new ArrayList[10001];
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j] == 1 && !visit[i][j]) {
					arrList[cnt-1] = new ArrayList<>();
					make_graph(new Point(j,i), cnt);
					cnt++;
					
				}
			}
		}
//		for(int i=0; i<n; i++) {
//			for(int j=0; j<n; j++) {
//				System.out.print(graph[i][j] +" ");
//			}System.out.println();
//		}
		
		
		for(int i=0; i<cnt-1; i++) {
			bfs(arrList[i]);
		}
		System.out.println(rs);
		
	}
	public static void bfs(ArrayList<Point> ar) {
		visit = new boolean[n][n];
		Queue<Point> q = new LinkedList<>();
		int val = graph[ar.get(0).y][ar.get(0).x];
		
		for(int i=0; i<ar.size(); i++) {
			int x = ar.get(i).x;
			int y = ar.get(i).y;
			visit[y][x] = true;
			q.add(new Point(x,y));
		}
		int result=0;
		while(!q.isEmpty()) {
			int size = q.size();
			for(int i=0; i<size; i++) {
				Point p = q.poll();
				int x = p.x;
				int y = p.y;
				
				for(int d=0; d<4; d++) {
					int newY = y + moveY[d];
					int newX = x + moveX[d];
					if(0<=newX && newX<n && 0<=newY && newY<n) {
						if(graph[newY][newX]!=0 && graph[newY][newX] != val) {
							
							rs = Math.min(rs, result);
//							System.out.println(y+" "+x+ " // " +newY+" "+newX + " // "+result);
							return;
						}else if(graph[newY][newX]==0 && !visit[newY][newX]) {
							visit[newY][newX] = true;
							q.add(new Point(newX,newY));
						}
					}
				}
				
				
			}
			result++;
		}
	}
	public static void make_graph(Point p, int cnt) {
		
		Queue<Point> queue = new LinkedList<Point>();
		
		queue.add(p);
		
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			
			int x = tmp.x;
			int y = tmp.y;
			arrList[cnt-1].add(new Point(x,y));
			
			visit[y][x] = true;
			graph[y][x] = cnt;
			
			for(int d=0; d<4; d++) {
				int newX = x + moveX[d];
				int newY = y + moveY[d];
				
				if(0<=newX && newX<n && 0<=newY && newY<n) {
					if(!visit[newY][newX] && arr[newY][newX]==1) {
						visit[newY][newX] = true;
						queue.add(new Point(newX,newY));
					}
				}
			}
			
		}
	}
}

 

 

 

'백준' 카테고리의 다른 글

#백준_1780 종이의 개수 - Java  (0) 2020.01.11
#백준_11728 배열 합치기 - Java  (0) 2020.01.11
#백준_1967 트리의 지름 - Java  (0) 2020.01.09
#백준_1167 트리의 지름 - Java  (0) 2020.01.09
#백준_1406 에디터  (0) 2020.01.03

 

https://ukyonge.tistory.com/17?category=870877

 

#백준_1167 트리의 지름 - Java

유형 : 트리 # 트리에서 탐색은 dfs,bfs가 많이 사용됨. 맨 처음에는 배열로 접근하여 dfs로 문제를 풀었으나, 메모리 초과가 나옴. 대신 인접리스트를 사용하여 문제를 해결하였더니 메모리 제한은 뜨지 않았음...

ukyonge.tistory.com

 

 

#위와 같은 방식으로 접근하여 풀 수있는 문제. 개인적으로는 1967번 문제를 먼저 풀고, 1167번 문제를 푸는 것을 추천.

지름을 구하는 법을 알지 못하면 한참동안 헤매는 문제.

 

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

package bj;

 

import java.awt.Point;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;

 

public class p1967 {

    static ArrayList<Point>[] arrList;

    static boolean visit[];

    static Point maxP;

    static int max=0;

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st;

        arrList = new ArrayList[n+1];

        visit = new boolean[n+1];

        for(int i=0; i<n+1; i++) {

            arrList[i] = new ArrayList<>();

        }

        for(int i=1; i<n; i++) {

            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());

            int b = Integer.parseInt(st.nextToken());

            int val = Integer.parseInt(st.nextToken());

            arrList[a].add(new Point(b,val));

            arrList[b].add(new Point(a,val));

        }

        

        Point tmp = dfs(arrList[1].get(0), 0);

        max = 0;

        maxP = null;

        visit = new boolean[n+1];

        

        dfs(tmp, 0);

        System.out.println(max);

    }

    

    public static Point dfs(Point p, int val) {

        visit[p.x] = true;

        

        for(Point tmp : arrList[p.x])

            if(!visit[tmp.x])

                dfs(tmp, val+tmp.y);

        

        if(max < val) {

            max = val;

            maxP = p;

        }

        

        return maxP;

    }

}

 

Colored by Color Scripter

 cs

 

'백준' 카테고리의 다른 글

#백준_11728 배열 합치기 - Java  (0) 2020.01.11
#백준_2146 다리 만들기 - Java  (0) 2020.01.09
#백준_1167 트리의 지름 - Java  (0) 2020.01.09
#백준_1406 에디터  (0) 2020.01.03
#백준_11652 카드  (0) 2020.01.01

유형 : 트리

# 트리에서 탐색은 dfs,bfs가 많이 사용됨.

맨 처음에는 배열로 접근하여 dfs로 문제를 풀었으나, 메모리 초과가 나옴. 대신 인접리스트를 사용하여 문제를 해결하였더니 메모리 제한은 뜨지 않았음. 

 

트리의 지름을 구하는 방법을 알아야 풀 수 있던 문제, 맨 처음에 dfs를 사용하여 가장 긴 길이를 갖고 있는 정점을 구한 후, 그 정점을 기준으로 다시 dfs를 사용하여 트리의 지름을 얻어야함.

 

트리의 지름 구하는법

1. 가장 긴 길이를 갖고있는 정점을 구한다.

2. 가장 긴 길이의 정점을 기준으로 다시 거리를 측정한다.

3. 거리를 저장한 배열 중 최대값이 트리의 지름이다.

 

1) 메모리 초과 났던 코드

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

package bj;

 

import java.awt.Point;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

 

public class p1167_memoryout {

    static int arr[][];

    static int n;

    static boolean visit[];

    static int max=0;

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        arr = new int[n+1][n+1];

        visit = new boolean[n+1];

        StringTokenizer st;

        for(int i=0; i<n; i++) {

            st = new StringTokenizer(br.readLine());

            int index = Integer.parseInt(st.nextToken());

            int next = Integer.parseInt(st.nextToken());

            int val = Integer.parseInt(st.nextToken());

            

            arr[index][next] = val;

            arr[next][index] = val;

            

            int tmp = Integer.parseInt(st.nextToken());

            while(tmp!=-1) {

                next = tmp;

                val = Integer.parseInt(st.nextToken());

                arr[index][next] = val;

                arr[next][index] = val;

                tmp = Integer.parseInt(st.nextToken());

            }

            

        }

        for(int i=1; i<=n; i++) {

            dfs(i,0);

//            System.out.println();

        }

        System.out.println(max);

    }

    

    public static void dfs(int v, int val) {

//        System.out.println(v+" "+val);

        visit[v] = true;

        max = Math.max(max, val);

        

        for(int i=1; i<=n; i++) {

            if(!visit[i] && arr[v][i]!=0) {

                dfs(i, val+arr[v][i]);

                visit[i] = false;

            }

        }

    }

}

 

Colored by Color Scripter

 cs

 

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

package bj;

 

import java.awt.Point;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.List;

import java.util.StringTokenizer;

 

public class p1167 {

    static int n, max = 0;

    static Point maxP;

    static boolean visit[];

    static List<Point>[] arrList;

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        

        arrList = new ArrayList[n+1];

        visit = new boolean[n+1];

        StringTokenizer st;

        

        for(int i=0; i<n+1; i++)

            arrList[i] = new ArrayList<>();

        

        for(int i=0; i<n; i++) {

            st = new StringTokenizer(br.readLine());

            int index = Integer.parseInt(st.nextToken());

            int next = Integer.parseInt(st.nextToken());

            int val = Integer.parseInt(st.nextToken());

            

            arrList[index].add(new Point(next, val));

            arrList[next].add(new Point(index, val));

            

            int tmp = Integer.parseInt(st.nextToken());

            while(tmp!=-1) {

                next = tmp;

                val = Integer.parseInt(st.nextToken());

                

                arrList[index].add(new Point(next,val));

                arrList[next].add(new Point(index, val));

                

                tmp = Integer.parseInt(st.nextToken());

            }

            

        }

        

        Point tmp = dfs(arrList[1].get(0), 0);

        visit = new boolean[n+1];

        maxP = null;

        max = 0;

        dfs(tmp, 0);

        System.out.println(max);

    }

    private static Point dfs(Point p, int val) {

        // TODO Auto-generated method stub

        visit[p.x] = true;

        

        for(Point t : arrList[p.x]) {

            if(!visit[t.x])

                dfs(t, val+t.y);

        }

        if(max < val) {

            max = val;

            maxP = p;

        }

        return maxP;

    }

}

 

Colored by Color Scripter

 cs

'백준' 카테고리의 다른 글

#백준_11728 배열 합치기 - Java  (0) 2020.01.11
#백준_2146 다리 만들기 - Java  (0) 2020.01.09
#백준_1967 트리의 지름 - Java  (0) 2020.01.09
#백준_1406 에디터  (0) 2020.01.03
#백준_11652 카드  (0) 2020.01.01

1. 조합(Combination)

서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!

 

2. 중복 조합(Combination with repetition)

서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n+r-1)C(r) (n-r+1)! /  ( (n-r)! * r!))

 

3. 순열(Permutation)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!

 

4. 중복 순열(Permutation with repetition)

서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^r

 

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

109

110

111

112

113

 

 

import java.util.ArrayList;

 

public class combination {

    static int arr[] =  { 1, 3, 5, 7, 9 };

    static boolean visit[] = new boolean[arr.length];

    static int cnt=0;

    static ArrayList<Integer> arrList = new ArrayList<>();

    public static void main(String[] args) {

        combination(arrList, arr.length, 3, 0);

        System.out.println("Count = "+cnt);

        System.out.println();

        cnt=0;

        

        arrList = new ArrayList<>();

        combination_repetition(arrList, arr.length, 3, 0);

        System.out.println("Count = "+cnt);

        System.out.println();

        cnt=0;

        

        arrList = new ArrayList<>();

        permutation(arrList, visit, arr.length, 3);

        System.out.println("Count = "+cnt);

        System.out.println();

        cnt=0;

        

        arrList = new ArrayList<>();

        permutation_repetition(arrList, arr.length, 3);

        System.out.println("Count = "+cnt);

    }

    

    // 조합 = 서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!

    public static void combination(ArrayList<Integer> arrList, int n, int r, int index) {

        if(r==0) {

            

            for(int i=0; i<arrList.size(); i++) {

                System.out.print(arrList.get(i)+" ");

            }System.out.println();

            cnt++;

            return;

        }

        

        if(index == n)

            return;

        

        arrList.add(arr[index]);

        combination(arrList, n, r-1, index+1); //뽑았음-> r-1

        arrList.remove(arrList.size()-1);    //위에서 뽑은거 롤백

        combination(arrList, n, r, index+1); //안뽑았으니 r

        

    }

    // 중복 조합 = 서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n-r+1)C(r) (n-r+1)! /  ( (n-r)! * r!))

    public static void combination_repetition(ArrayList<Integer> arrList, int n, int r, int index) {

        if(r==0) {

            for(int i=0; i<arrList.size(); i++) {

                System.out.print(arrList.get(i)+" ");

            }System.out.println();

            cnt++;

            return;

        }

        

        if(index == n)

            return;

        

        arrList.add(arr[index]);

        combination_repetition(arrList, n, r-1, index); //뽑았음-> r-1 중복을 허용하니까 index는 고정

        arrList.remove(arrList.size()-1);    //위에서 뽑은거 롤백

        combination_repetition(arrList, n, r, index+1); //안뽑았으니 r, index+1

        

    }

    

    // 순열 = 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!

    public static void permutation(ArrayList<Integer> arrList, boolean[] visit, int n, int r) {

        if(arrList.size() == r) {

            for(int i : arrList) {

                System.out.print(i+" ");

            }System.out.println();

            cnt++;

            return;

        }else {

            for(int i=0; i<n; i++) {

                if(!visit[i]) {

                    visit[i] = true;

                    arrList.add(arr[i]);

                    permutation(arrList, visit, n, r);

                    arrList.remove(arrList.size()-1);

                    visit[i] = false;

                }

            }

        }

    }

    // 중복 순열 = 서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^r

    public static void permutation_repetition(ArrayList<Integer> arrList, int n, int r) {

        if(arrList.size() == r) {

            for(int i : arrList) {

                System.out.print(i+" ");

            }System.out.println();

            cnt++;

            return;

        }else {

            for(int i=0; i<n; i++) {

                

                arrList.add(arr[i]);

                permutation_repetition(arrList, n, r);

                arrList.remove(arrList.size()-1);

            

            }

        }

    }

        

}

 

Colored by Color Scripter

 cs

'알고리즘' 카테고리의 다른 글

#알고리즘_플로이드 와샬(Floyd-Warshall Algorithm) - Java  (0) 2020.01.11
#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java  (0) 2020.01.11
#알고리즘_선형 탐색/이진 탐색 - Java  (0) 2020.01.08
#알고리즘_신장 트리(Spanning Tree)  (0) 2020.01.08
#알고리즘_프림(Prim Algorithm) - Java  (0) 2020.01.08

1. 선형 리스트(ArrayList)

 배열과 같이 연속되는 기억장소에 저장되는 리스트

선형 리스트의 특징

  1. 가장 간단한 자료구조이다.

  2. 접근속도가 빠르다.

  3. 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.

  4. 기억장소를 연속적으로 배정하기 때문에 기억장소 사용 효율은 밀도가 1로서 가장 좋다.

  5. 자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2이다.

  6. 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거롭다.

2. 연결 리스트(LinkedList)

연결 리스트는 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라 노드의 포인터 부분을 이용하여 연결시킨 자료 구조

연결 리스트의 특징

  1. 노드의 삽입, 삭제 작업이 용이하다.

  2. 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.

  3. 연결을 위한 포인터가 필요하기 때문에 선형 리스트에 비해 기억공간 이용 효율이 좋지 않다.

  4. 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

  5. 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

  6. 희소 행렬 을 링크드 리스트로 표현하면 기억장소가 절약된다.

  7. 노드 구조를 사용하는 트리 등을 표현할 때 가장 적합한 자료 구조이다.

'자료구조' 카테고리의 다른 글

#자료구조_03_트리  (0) 2020.01.03
#자료구조_02_스택, 큐, 데크  (0) 2020.01.03
#자료구조_01_데이터구조분류  (0) 2020.01.01

탐색 문제를 해결하는 방법 2가지 

  • 선형 탐색(순차 검색) :  순서대로 하나씩 비교하면서 찾기
  • 이진 탐색 : 반씩 범위를 줄여 나가면서 찾기

선형 탐색은 순서대로 하나씩 비교하면서 찾는 방법으로 시간 복잡도는 O(N)이다.

 

이진 탐색은 크기를 비교하며 반씩 줄여나가므로 배열이 정렬되어있다는 가정하에 진행한다. 따라서 배열이 정렬 되어있지 않다면 이진 탐색을 사용할 수 없다. 이진 탐색의 시간 복잡도는 O(log N)이다.

 

이진 탐색의 장점은 선형 탐색보다 탐색 속도가 빠르지만, 정렬되어 있어야 한다는 단점이 있다.

 

이진 탐색의 메카니즘

정렬된 배열의 중간에 임의의 값을 찾고자하는 값과 비교하여

1) 만약 중간의 값이 더 작다면 중간의 값을 제외한 배열의 우측 데이터들을 대상으로 탐색을 진행한다.

2) 만약 중간의 값이 더 크다면 중간의 값을 제외한 배열의 좌측 데이터들을 대상으로 탐색을 진행한다.

3) 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

import java.util.Arrays;

 

public class search {

    public static void main(String[] args) {

        int arr[] = { 12,4,7,2,9,15,29,41};

        System.out.println(linear_search(arr, 2));

        

        Arrays.sort(arr);

        System.out.println(binary_search(arr, 2));

    }

    

    public static int linear_search(int arr[], int val) {

        

        for(int i=0; i<arr.length; i++) {

            if(arr[i] == val) {

                return i;

            }

        }

        return -1;

    }

    

    public static int binary_search(int arr[], int val) {

 

        int begin = 0;

        int end = arr.length-1;

        int middle;

        

        while(begin<=end) {

            middle = (begin+end)/2;

            if(val == arr[middle])

                return middle;

            else if(val > arr[middle]) {

                begin = middle + 1;

            }else {

                end = middle-1;

            }

        }

        return -1;

    }

}

 

Colored by Color Scripter

 cs

'알고리즘' 카테고리의 다른 글

#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java  (0) 2020.01.11
#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java  (0) 2020.01.09
#알고리즘_신장 트리(Spanning Tree)  (0) 2020.01.08
#알고리즘_프림(Prim Algorithm) - Java  (0) 2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java  (0) 2020.01.07

신장 트리 (Spanning Tree)

1. 그래프의 모든 정점이 간선으로 연결되어 있다.

2. 그래프 안에 사이클이 포함되어 있지 않다.

 

최소 신장 트리(Minimum Spanning Tree)

말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리

 

 

Prim, Kruskal 알고리즘은 최소 신장 트리를 구하는 방법이다. 두 알고리즘 모두 Greedy Method를 기반으로 한다.

'알고리즘' 카테고리의 다른 글

#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java  (0) 2020.01.09
#알고리즘_선형 탐색/이진 탐색 - Java  (0) 2020.01.08
#알고리즘_프림(Prim Algorithm) - Java  (0) 2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java  (0) 2020.01.07
#알고리즘_다익스트라(Dijkstra Algorithm) - Java  (0) 2020.01.07

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 알고리즘이다.

쉽게 말하면 프림 알고리즘은 지금까지 연결된 정점에서 연결된 간선들 중 사이클을 만들지 않고 최소의 값을 갖는 간선을 하나씩 선택하면서 MST를 만들어가는 방식이다.

 

프림 알고리즘은 시작 정점을 정하고, 시작 정점에서 가까운 정점을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않는다. 그에 반해 크루스칼 알고리즘은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 한다. 이 때, Union-Find(Disjoint-Set) 방법을 이용하여 사이클을 확인한다.

시간 복잡도

  • 프림 : O(V^2+E) → O(E logV)
  • 크루스칼 : O(E logE)

 

**프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘

**시간 복잡도는 비슷하지만, 보통 밀집한 그래프의 경우 프림이, 그렇지 않은 경우에는 크루스칼이 유리하다.

 

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

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Queue;

import java.util.Scanner;

 

public class prim {

    

    static int V,E;

    static boolean visit[];

    static ArrayList<Edge>[] graph;

    static ArrayList<Edge> MST;

    

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

 

        V = sc.nextInt();

        E = sc.nextInt();

        

        graph = new ArrayList[V+1];

        visit = new boolean[V+1];

        

        for(int i=0; i<=V; i++) 

                graph[i] = new ArrayList<>();

        

        MST = new ArrayList<>();

        

        for(int i=1; i<=E; i++) {

                int u = sc.nextInt();

                int v = sc.nextInt();

                int val = sc.nextInt();

                

                graph[u].add(new Edge(u, v, val));

                graph[v].add(new Edge(v, u, val));

        }

        int point = 1;

        solve(point);

        

        for(int i=0; i<MST.size(); i++) {

                System.out.println(MST.get(i).begin + " " +MST.get(i).end+" "+MST.get(i).value);

        }

    }

    

    

    private static void solve(int P) {

        // TODO Auto-generated method stub

 

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        Queue<Integer> queue = new LinkedList<>();        

        

        queue.add(P);

        

        while(!queue.isEmpty()) {

                int now = queue.poll();

                visit[now] = true;

                

                for(Edge e : graph[now]) {

                    if(!visit[e.end])

                        pq.add(e);

                }

                

                while(!pq.isEmpty()) {

                    Edge e = pq.poll();

                    if(!visit[e.end]) {

                        queue.add(e.end);

                        visit[e.end] = true;

                        MST.add(e);

                        break;

                    }

                }

        }

        

    }

 

 

    public static class Edge implements Comparable<Edge>{

        int begin;

        int end;

        int value;

        

        public Edge(int b, int e, int v) {

            this.begin = b;

            this.end = e;

            this.value = v;

        }

        

        

        @Override

        public int compareTo(Edge o) {

            // TODO Auto-generated method stub

            return this.value - o.value;

        }

        

    }

}

 

Colored by Color Scripter

 cs

'알고리즘' 카테고리의 다른 글

#알고리즘_선형 탐색/이진 탐색 - Java  (0) 2020.01.08
#알고리즘_신장 트리(Spanning Tree)  (0) 2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java  (0) 2020.01.07
#알고리즘_다익스트라(Dijkstra Algorithm) - Java  (0) 2020.01.07
#알고리즘_정렬(Insertion, Bubble, Selection, Quick, Heap, Merge) - Java  (0) 2020.01.06

+ Recent posts

티스토리툴바