탐욕적인 방법(greedy method) 을 이용하여 

네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

1) cost 기준으로 오름차순 정렬

2) 정렬된 그래프를 기준으로 간선연결

 - 간선은 필요한 간선만 연결
 - 필요한 간선이란? 기 연결된 정점은 해당 간선을 이용해 연결하지 않는다
 즉, 어떤 두 정점이 연결됐는지 안됐는지 확인하는 연산필요 -> union find 이용 
 1) find(a) != find(b) => 연결 (union(a,b))
 2) find(a) = find(b) => 연결 X

 

 

    static long kruskal(int startIdx) {
        initParent();
        for (int i = startIdx; i < M; i++) {
            Edge edge = list.get(i);
            if (find(edge.e) == find(edge.s)) { // 같은 그룹이면 연결 안함
                continue;
            }
            union(edge.s, edge.e); // 다른그룹이므로 연결함
        }
        return -1; // 연결 안되어 있음
    }

대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.

상호 배타적 집합(Disjoint-set)이라고도 합니다.

여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

즉, 그래프에서 같은 그룹에 속하는가? 를 물어볼 수 있는 알고리즘이다.

혹은 그룹을 합치거나

 

 

1. 초기화 ( make set)

자기자신을 부모로 갖도록 초기화 해준다.

int[] parent = new int[N+1];
for(int i = 0 ; i <= N ; i ++){
	parent[i] = i;
}

 

 

2. find

int find(int a){
	if(a == parent[a]) return a;
	return parent[a] = find(parent[a]); // 경로 압축

}

시간복잡도 O(N)

 

원래 return 부가 

return find(parent[a]) 인데 

return parent[a] = find(parent[a]) 로 경로 압축을 해주었다. 한번에 가기~!

 

3. union

void union(int a, int b){
	a = find(a);
	b = find(b);
	
	if(a != b){
		//항상 더 작은수로 부모를 넣어준다.
		if(a > b){ // a가 항상 작은수가 되도록 만듦
              int tmp = a;
              a = b;
              b = tmp;
        }
        parent[b] = a;
	}
}

 

4. 문제 풀기

1. 계속 합쳐지는 패턴 
2. 계속 분리되는 패턴 
 - 질문의 역순으로 답을 내야함 

  => 질문을 미리 저장해두고, 질문의 역순으로 답을 낸다. 

  
3. 그룹의 멤버의 수 
4. 유효/무효 값 분리 

LCA는 트리를 이용해서 최단거리 알고리즘을 구하는 것이다.

최소 공통조상을 구하는 알고리즘이다. Lowest Common Ancestor

 

구현

 

0. dfs or bfs depth , parent[N][K] : N번 노드의 2^K번째 조상 기록


parent[2][0] = 2번 노드의 첫번째 조상
parent[2][1] = 2번 노드의 두번째 조상
parent[2][2] = 2번 노드의 네번째(2^2) 조상

 

dfs로 구현하면 stack이 터질 수 있으니, bfs로 구현하는 것이 좋다.

 

2^K번째 조상을 기록 한다는것이 잘 이해가 안갈 수 있다. 왜 2^K번째 조상을 기록할까? 시간복잡도를 줄이기 위해서이다.

 

다음을 보자. 1에서 12로 이동할때 


이진법으로 움직이면?
1->2->-3->4->5->6->7->8->9->10  ->11         ->12 :  한칸씩 뛰면 11번 이동, 비효율적임
1--------(2^3)---------->9-----(2^1)---->11-(2^0)->12 :  2진법으로 움직이면 3번 이동, 효율적임

 

규칙을보면 다음과 같은 점화식을 얻을 수 있다.

parent[N][K] = parent[parent[N][K-1]][K-1];

A ------------> C                parent[A][4] = C
1               17

A ----- B ----> C                parent[A][3] = B , parent[B][3] = C
1        9        17               parent[A][4] = parent[parent[A][3]][3]

 

 

1. LCA 로직

 1) 양쪽 노드중 깊이가 깊은 것을 끌어올려 깊이를 맞춘다.( 2진법으로 뛸 수 있는 만큼 높이 뛰기)


 2) if(a == b) return a;


 3) else 높이가 맞춰진 양쪽 노드를 동시에 끌어올린다. 

    단 2진법으로 뛸수 있는만큼 뛰는데, ***부모가 다를경우에만 점프

 

 4) return parent[a][0]; // a또는 b의 부모 

 

 

샘플코드

 

BFS

 

    static int MAX =18;
    static int[] depth = new int[MAX];
    static int[][] parent = new int[MAX][32];
    // 2^k = N -> k = logN : parent배열의 열의 사이즈는 logN
    // 2^10 = 10^3 , 2^40 = 2^10^4 = 10^3^4 = 10^12
    // 2^17 = 13만 , 2^18 = 26만 , 2^20 = 104만

    static boolean[] visited = new boolean[MAX];
    static ArrayList<Integer>[] adj = new ArrayList[MAX];
    
    static void bfs(int now) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(now);

        while (!q.isEmpty()) {
            now = q.poll();
            visited[now] = true;
            for (int next : adj[now]) {
                if (visited[next]) continue;

                parent[next][0] = now;
                for (int j = 1; j < MAX; j++) {
                    parent[next][j] = parent[parent[next][j - 1]][j - 1];
                }

                depth[next] = depth[now] + 1; //// next의 depth는 현재의 depth++;
                q.add(next);

            }
        }
    }

 

LCA

 

    static int LCA(int a, int b) {
        // detph 맞추기
        // 0. 항상 a보다 b가 아래에 있는 상태로 만들어주기
        if (depth[a] > depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        //1. 양쪽 노드의 깊이를 맞춰주기 (B를 A가 있는 depth까지 끌어올리기)
        // 1 ---------->12 몇층 이동할까?
        // 12---->4-->2->1
        for (int i = MAX-1; i >= 0; i--) {
            if (depth[b] - depth[a] >= (1 << i)) { // 2^i : 이동할 수 있는만큼 이동하기
                b = parent[b][i];
            }
        }

        // 2. a,b 높이가 맞춰진 상태 - 현재 위치가 LCA인 경우?
        if (a == b) { return a; }
        //3. 양쪽을 동시에 2진법으로 끌어올릴수 있는 만큼 끌어올리는데,단 부모가 다르면 이동
        for (int i = MAX-1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) { //부모가 다르면 이동
                a = parent[a][i];
                b = parent[b][i];
            }
        }

        return parent[a][0];
    }

N to N ( N<=500)

출발지와 도착지 모두 N개일때 쓰는 알고리즘

시간복잡도가 O(N^3)이므로 N이 적을때만 사용 가능하다.

 

i지점에서 j 지점까지 갈때의 최단거리가

k 지점을 거쳐서 가면 어느것이 더 최단거리일까? 라는것을 구해주면 된다.

 

 

샘플 코드

    
    static int[] d;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static void floyd() {
        //1. d배열 INF 채우기
        Arrays.fill(d, INF);

        //2. 입력값으로 들어오는 간선 cost 받기 adj

        for (int k = 1; k <= N; k++) { //경유지가 밖에 있어야함.-> 대상이 되는 경유지를 고정 해야함.
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

두번째로 벨만포드를 정리해보고자 한다.

 

음수 가중치가 있을때 최단거리를 구하는 알고리즘이다.

 

V번 E개의 간선에 대해 dist 배열 갱신한다.
* V번째에 dist 배열의 갱신이 발생하면 -> 음의 사이클 존재

 

요 음의 사이클이 존재 하는지 안하는지가 벨만포드에서 가장 중요하다.

이유는? (V-1)번까지 돌았는데 V번째에서 dist 배열 갱신이 발생한다면?

사이클이 있는데 그값이 계속 감소한다는 것이다. 가중치가 음수가 있기 때문에 가능한 현상이다.

 

그래서 문제를 풀다보면 음의 사이클이 있는가? 를 묻는 문제도 더러 있다

 

 

 

 

샘플코드 

    static int[] dist;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static int belman() {
        //1. dist 배열 INF 값으로 채우기, 출발지는 0으로
        Arrays.fill(dist, INF);
        dist[1] = 0;

        //2. V번 E개의 간선은 탐색 (음수 사이클 체크를 위해 V-1+1번 체크)
        boolean isUpdated;
        for (int i = 1; i <= N; i++) { // V
            isUpdated = false;
            for (int here = 1; i <= N; here++) {// E
                for (Node next : adj[here]) {//dist 배열 업데이트
                    int nextCost = dist[here] + next.cost;
                    if (dist[here] != INF && dist[next.idx] > nextCost) {
                        //dist[here] != INF : 연결이 안된다는 것을 확인 , 현재노드인 here가 이전에 방문했어야함 그래야 거쳐서 가니깐 
                        dist[next.idx] = nextCost;
                        isUpdated = true;
                    }
                }
                if (!isUpdated) break; // 더 이상 최단 경로 갱신이 안일어 나면 조기종료
            }
            if (isUpdated) return -1;
        }
        return dist[N];
    }

 

 

+ Recent posts