hyeoneee's blog

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

상호 배타적 집합(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];
    }

어떤 정점에서 출발해서 모든 노드들로 가기까지 최단거리들을 구하는 알고리즘

특징

1. 음의 가중치가 없다. 무조건 양의 가중치이다.

-> 가중치가 모두 같으면? BFS로푼다.

2. 이전에 풀었던 부분 최단거리가 최단거리임을 보장한다.

3. Priority Queue를 사용하여 가중치순으로 정렬한다.

Priority Queue<Node> pq = new Priority Queue <>( (o1,o2)->Long.compare(o1.cost,o2.cost);

pq를 사용하는 이유?

• Cost순으로 정렬되기 위해, 거리가 적은 순으로 뽑아서 그 노드를 거쳐서 가면
• 최소임이 보장되기 때문에 pq를 사용한다.

4. 최단거리 배열은 MAX값으로 초기화 시켜준다 ( 최단거리를 구하기 위해)

5. 인접배열은 양방향, 단방향을 고려해준다.

응용

1. 왔다 갔다 최단거리 (출발 -> 도착 정점 -> 출발)

-  출발정점에서 최단거리 구하고 도착정점에서 최단거리 더해서 두개 더해

2. 단일 도착 지점에 대한 최단거리 (1~N-1 번 정점에서 출발 N번 도착)

- 반대로 N에서 출발해서 최단거리 구하기

3. 여러 지점에서 출발하는 최단거리

- 가상의 출발지점에서 가중치 0으로 출발 지점들을 연결한 후 최단거리 구하기

4. 최단거리의 경우의 수 구하기 ( 백준 14554 )

 - 배열하나를 더 선언해, 최단거리로 업데이트 하면, 다음 경로로 가는 경우의 수에 기존 경로의 수를 넣어주고,

   최단거리가 같으면? 해당 지점에 오는 경우의수가 늘어나는 것이므로, 

   다음 경로의 수에 기존경로+ 다음경로를 더해준다.

                        if (dist[newX][newY] > dist[now.x][now.y] + cost) { // 최단거리 업데이트
                            dist[newX][newY] = dist[now.x][now.y] + cost;
                            pq.add(new Node(newX, newY, dist[newX][newY], 0));
                            path[newX][newY] = path[now.x][now.y];
                        } else if (dist[newX][newY] == dist[now.x][now.y] + cost) { // 최단거리가 같으면
                            path[newX][newY] = path[now.x][now.y] + path[newX][newY]; // 경우의수 누적
                        }

샘플 코드

    static int[] dist;
    static int N;
    static PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.cost,o2.cost));
    static ArrayList<Node>[] adj = new ArrayList[N+1]; // main에서 초기화 필요 
	static void dijkstra() {
        //0. 초기화 dist 배열 INF 값으로 채우기 , 시작점은 0, q에 시작점 add
        Arrays.fill(dist, INF);
        dist[1] = 0;
        pq.add(new Node2(1, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (dist[now.idx] < now.cost) { // 현재 노드의 최소거리가 가져온 cost 보다 작다면 넘어가도됨
                continue; // 이미 최단거리를 확정했으면 돌필요가없음 아니면 시간초과
            }
            for (Node next : adj[now.idx]) {
                if (dist[next.idx] > dist[now.idx] + next.cost) { // 최단거리이면
                    dist[next.idx] = dist[now.idx] + next.cost; // 거리 업데이트 해주고
                    pq.add(new Node(next.idx, dist[next.idx]); // pq에 값 넣기 -> cost : 업데이트된 거리값
                }
            }
        }
    }