hyeoneee's blog

어떤 일을 하는 순서를 찾는 알고리즘이다.

DAG 란

1. 노드간의 순서가 있을때 

2. 사이클이 없을때 -> 사이클 판단 가능

3. 시간복잡도 O(V+ E)

dfs , bfs 모두 가능하다. bfs로 구현해보도록 하겠다.

DAG는 노드간의 순서가 있기 때문에

진입차수가 0인것을 queue에 넣어서 BFS를 진행해 보도록 하겠다.

Dfs

	for( n of All){
		if(!visited[n]) dfs(n);
	}
	
	dfs(int now){
		visited[now] = true;
		for(next : adj){
			if(!visited[next]) dfs(next);
		}
		stack.push(now);	//dfs 나오는 순서대로 stack에 쌓아준다. 
	}

Bfs

  static int bfs() { //위상정렬 DAG
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0; 
       		
         for(int i = 1 ;i <= indegree.size()-1 ; i ++){
			if(indegree[i]==0){ // 인디그리가 없으면 큐에 넣어준다.
				q.add(i);
           }
	}

        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;
            for (Node next : adj[now]) {
                indegree[next.n]--; //next에 방문했으니 진입차수 줄여주기
                // next에 오기까지 위한 최대 dist 구해주기 그래야 다음을 갈 수 있음
                dist[next.n] = Math.max(dist[next.n], dist[now] + next.cost);
                if (indegree[next.n] == 0) {
                    q.add(next.n);
                }
            }
        }
        
        return cnt != N // cnt가 N이 아니면 사이클이 있음
    }

응용

1. 순서 찾기

2. 사이클 찾기

3. 문제 조건에 따라 순서 부여해 풀기

4. 위상정렬 + 동적 계획법

5. 사이클 없애가는 문제 

탐욕적인 방법(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]);
                }
            }
        }
    }