ㄴㄴ 내가 더 빠름(feat. MST)

leverest96·2023년 3월 30일
0
post-thumbnail

Disjoint sets

  1. Disjoint sets(서로소 집합) : MST를 위한 기본 지식
    • 서로 중복 포함된 원소가 없는 집합들
      • 즉, 교집합이 없다.
    • 집합에 속한 하나의 특정 멤버(대표자 / representative)를 통해 각 집합들을 구분
    • 표현하는 방법
      • 연결 리스트
      • 트리
    • 연산 + Pseudo Code
      • Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
        Make-set(x)
            p[x] ← x
      • Find-Set(x) : x를 포함하는 집합을 찾는 연산
        Find-Set(x)
            IF x == p[x] : RETURN x
            ELSE : RETURN Find-Set(p[x])
      • Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
        Union(x, y)
            p[Find-Set(y)] ← Find-Set(x)
    • 연산의 효율을 높이는 방법
      • Rank를 이용한 Union
        • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크라는 이름으로 저장
        • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
      • Path compression
        • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다.
      • Pseudo Code
        • Make-Set(x)

          p[x] : 노드 x의 부모 저장
          rank[x] : 루트 노드가 x인 트리의 랭크 값 저장
          
          Make-set(x)
              p[x] ← x
              rank[x] ← 0
        • Find-Set(x) : x를 포함하는 집합을 찾는 연산

          Find-Set(x)
              IF x != p[x] :  // x가 루트가 아닌 경우
                  p[x] ← Find-Set(p[x])
              RETURN p[x]
        • Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산

          Union(x, y)
              Link(Find-Set(x), Find-Set(y))
           
          Link(x, y)
              IF rank[x] > rank[y] :
                  p[y] ← x
              ELSE
                  p[x] ← y
                  IF rank[x] == rank[y] :
                      rank[y]++

MST(Minimum Spanning Tree)

  1. Minimum Spanning Tree(최소 비용 신장 트리)
    • Spanning Tree(신장 트리) : 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리
    • MST : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
    • 특징
      • 무방향 가중치 그래프
      • 그래프의 가중치의 합이 최소여야 한다.
      • N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다.
      • 사이클을 포함해서는 안된다.

KRUSKAL Algorithm

  1. KRUSKAL Algorithm : 간선을 하나씩 선택해서 MST를 찾는 알고리즘

    • 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

    • 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

      • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
    • n-1개의 간선이 선택될 때까지 2를 반복

    • Pseudo Code

      MST-KRUSKAL(G, w)
          A ← 0  // 0 : 공집합
          FOR vertex v in G.V  // G.V : 그래프의 정점 집합
              Make-Set(v)  // G.E : 그래프의 간선 집합
              
          G.E에 포함된 간선들을 가중치 w에 의해 정렬
          
          FOR 가중치가 가장 낮은 간선 (u, v) ∈ G.E 선택(n-1개)
              IF Find-Set(u) ≠ Find-Set(v)
                  A ← A ∪ {(u, v)}
                  Union(u, v)
                  
          RETURN A;
    • Code

      static int[] arr, p;
      static int V, E;
      
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
          StringTokenizer st = new StringTokenizer(br.readLine());
      
          V = Integer.parseInt(st.nextToken());  // V : 정점의 개수, 0부터 시작
          E = Integer.parseInt(st.nextToken());  // E : 간선의 수
      
          arr = new int[V];
      
          // 간선을 저장하기 위해서 클래스를 사용할 수도 있지만
          // 배열을 이용해서 저장할 예쩡
          // 0 : 시작정점 / 1 : 끝정점 / 2 : 가중치
          int[][] edges = new int[E][3];
      
          for (int i = 0; i < E; i++) {
              st = new StringTokenizer(br.readLine());
              edges[i][0] = Integer.parseInt(st.nextToken());
              edges[i][1] = Integer.parseInt(st.nextToken());
              edges[i][2] = Integer.parseInt(st.nextToken());
          }
      
          // 크루스칼 1단계 : 간선 오름차순으로 정렬
          Arrays.sort(edges, new Comparator<int[]>() {
              @Override
              public int compare(int[] o1, int[] o2) {
                  return o1[2] - o2[2];
              }
          });
      
          // 크루스칼 2단계 : V-1개의 간선을 뽑는데, 사이클이 발생 안하는 녀석들만 선택
          p = new int[V];
          // make-set
          for (int i = 0; i < V; i++) {
              makeset(i);
          }
      
          int ans = 0; // 최소비용을 저장할 변수
          int pick = 0; // 뽑은 간선의 수
      
          // 모든 간선을 순회하면서 체크
          for (int i = 0; i < E; i++) {
              // i번째의 간선을 뽑아 두 정점의 대표를 확인
              int x = edges[i][0];
              int y = edges[i][1];
      
              if (findset(x) != findset(y)) {
                  union(x, y);
                  ans += edges[i][2];
                  pick++;
              }
      
              if (pick == (V-1)) break;
          }
      
          bw.write(ans);
      
          bw.flush();
          bw.close();
      }
      
      static void makeset(int x) {
          p[x] = x;
          // Rank 따로 설정 X
      }
      
      // 대표를 반환해야 하므로
      static int findset(int x) {
          // 순수 기술
          // if (x == p[x]) return x;
          // return findset(p[x]);
      
          // path compression 적용
          if (x != p[x]) p[x] = findset(p[x]);
          return p[x];
      }
      
      static void union(int x, int y) {
          p[findset(y)] = findset(x);
          // Rank 고려 X, 그냥 무조건 y를 x 밑으로 설정
      }

PRIM Algorithm

  1. PRIM Algorithm : 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 가는 방식

    • 과정

      • 임의 정점을 하나 선택해서 시작
      • 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
      • 모든 정점이 선택될 때까지 1, 2 과정 반복
    • 서로소인 2개의 집합 정보를 유지

      • 트리 정점들(tree verticles) : MST를 만들기 위해 선택된 정점들
      • 비트리 정점들(nontree verticles) : 선택되지 않은 정점들
    • Code : priority queue를 이용할 수도 있고 반복문을 이용할 수도 있다.

      • 단, 다익스트라 알고리즘에서 pq를 쓸 예정이라 pq를 포함한 걸로 공부하자.

      • priority queue를 사용한 구현

        static boolean[] visited;
        static int V, E;
        
        static class Edge implements Comparable<Edge> {
            int st, ed, w;
        
            public Edge(int st, int ed, int w) {
                this.st = st;
                this.ed = ed;
                this.w = w;
            }
        
            @Override
            public int compareTo(Edge o) {
                return Integer.compare(this.w, o.w);
            }
        }
        
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
            StringTokenizer st = new StringTokenizer(br.readLine());
        
            V = Integer.parseInt(st.nextToken());  // V : 정점의 개수, 0부터 시작
            E = Integer.parseInt(st.nextToken());  // E : 간선의 수
        
            List<Edge>[] adjList = new ArrayList[V];
        
            for (int i = 0; i < V; i++) {
                adjList[i] = new ArrayList<>();
            }
        
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken()); // 시작 정점
                int B = Integer.parseInt(st.nextToken()); // 도착 정점
                int W = Integer.parseInt(st.nextToken()); // 가중치
                // 무향 그래프이므로
                adjList[A].add(new Edge(A, B, W));
                adjList[B].add(new Edge(B, A, W));
            }
        
            visited = new boolean[V]; // 방문 처리를 위한 용도
        
            PriorityQueue<Edge> pq = new PriorityQueue<>();
        
            // 시작정점을 하나 뽑고 시작
            visited[0] = true; // 0번 정점을 기준으로 시작
        
            // 1
            // for (int i = 0; i < adjList[0].size(); i++) {
            // pq.add(adjList[0].get(i));
            // }
        
            //2
            // for (Edge e : adjList[0]) {
            //     pq.add(e);
            // }
        
            // 위 두가지 방식과 같은 역할
            pq.addAll(adjList[0]);
        
            int pick = 1; // 확보한 정점의 개수
            int ans = 0;
        
            // pick < V 일 때 반복
            while (pick != V) {
                Edge e = pq.poll();
                if (visited[e.ed]) continue;
        
                ans += e.w;
                pq.addAll(adjList[e.ed]);
                visited[e.ed] = true;
                pick++;
            }
        
            bw.write(ans + "");
        
            bw.flush();
            bw.close();
        }
      • 반복문을 이용한 구현

        static int[][] adjArr;
        static int[] p, dist;
        static boolean[] visited;
        static int V, E, ans;
        static final int INF = Integer.MAX_VALUE;
        
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
            StringTokenizer st = new StringTokenizer(br.readLine());
        
            V = Integer.parseInt(st.nextToken());  // V : 정점의 개수, 0부터 시작
            E = Integer.parseInt(st.nextToken());  // E : 간선의 수
        
            adjArr = new int[V][V];
        
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken()); // 시작 정점
                int B = Integer.parseInt(st.nextToken()); // 도착 정점
                int W = Integer.parseInt(st.nextToken()); // 가중치
                // 무향 그래프이므로
                adjArr[A][B] = W;
                adjArr[B][A] = W;
            }
        
            visited = new boolean[V]; // 방문 처리를 위한 용도
            p = new int[V]; // 어디에서 왔는지에 대한 정보를 저장하는 용도
            dist = new int[V]; // key라고 불리는 가장 작은 값을 저장하는 용도
        
            // dist 배열의 모든 원소를 아주 큰 값으로 갱신
            for (int i = 0; i < V; i++) {
                dist[i] = INF;
            }
            // 위와 동일한 역할
            // Arrays.fill(dist, INF);
        
            // 임의의 한점을 선택해서 시작
            dist[0] = 0; // 0번 정점을 기준으로 시작
            p[0] = -1;
        
            ans = 0;
        
            // 정점 개수만큼 반복해도 되지만
            // 마지막에는 이미 모든 간선 가중치를 확인했으므로 굳이 필요없다.
            // 프림 동작
            for (int i = 0; i < V-1; i++) {
                // 1. 가장 작은 값을 선택
                int min = INF;
                int idx = 0;
        
                // 아직 안뽑힌 정점 중 가장 작은 값 선택
                for (int j = 0; j < V; j++) {
                    if (!visited[j] && dist[j] < min) {
                        min = dist[j];
                        idx = j;
                    }
                } // idx에는 가장 작은 값을 가지고 있는 정점 번호가 저장
                visited[idx] = true; // 선택
        
                // 2. 뽑은 정점을 이용해서 갱신할 수 있는게 있다면 모두 갱신
                // 인접 행렬이므로 모든 정점을 확인하는 것
                for (int j = 0; j < V; j++) {
                    if (!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
                        dist[j] = adjArr[idx][j];
                        p[j] = idx;
                    }
                }
            }
        
            for (int i = 0; i < V; i++) {
                ans += dist[i];
            }
        
            bw.write(ans + "");
        
            bw.flush();
            bw.close();
        }

최단 경로

  1. 정의
    • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
  2. 하나의 시작 정점에서 끝 정점까지의 최단경로
    • Dijkstra algorithm(다익스트라 알고리즘) : 음의 가중치 미허용
    • Bellman-Ford algorithm(벨만-포드 알고리즘) : 음의 가중치 허용
  3. 모든 정점들에 대한 최단경로
    • Floyd-Warshall algorithm(플로이드-워샬 알고리즘)

DIJKSTRA Algorithm

  1. DIJKSTRA Algorithm : 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식

    • 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사

    • 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다.

    • 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.

    • 동작 과정

      • 시작 정점을 입력 받는다.
      • 거리를 저장할 D 배열을 ∞로 초기화한 후 시작점에서 갈 수 있는 곳의 값은 바꿔 놓는다.
      • 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치의 합이 작다면 변경하여 적는다.
      • 모든 정점을 방문할 때까지 반복
    • Code

      • 공통 부분

        static final int INF = Integer.MAX_VALUE;
        static int V, E;
        static List<Node>[] adjList;
        static int[] dist;
        
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
            StringTokenizer st = new StringTokenizer(br.readLine());
        
            V = Integer.parseInt(st.nextToken());  // V : 정점의 개수, 0부터 시작
            E = Integer.parseInt(st.nextToken());  // E : 간선의 수
        
            adjList = new ArrayList[V];
            for(int i = 0 ; i<V; i++)
                adjList[i] = new ArrayList<>();
        
            dist = new int[V];
            Arrays.fill(dist, INF);
        
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken()); // 시작 정점
                int B = Integer.parseInt(st.nextToken()); // 도착 정점
                int W = Integer.parseInt(st.nextToken()); // 가중치
                // 유향 그래프이므로
                adjList[A].add(new Node(B, W));
            }
        
            dijkstra(0);
        
            bw.write(Arrays.toString(dist));
        
            bw.flush();
            bw.close();
        }
      • priority queue를 이용한 구현

        static class Node implements Comparable<Node> {
            int v, w;
            public Node(int v, int w) {
                this.v = v;
                this.w = w;
            }
        
            @Override
            public int compareTo(Node o) {
                return Integer.compare(this.w, o.w);
            }
        }
        
        private static void dijkstra(int start) {
            PriorityQueue<Node> pq = new PriorityQueue<>();
        
            pq.offer(new Node(start, 0));
        
            dist[start] = 0; // 시작 노드까지의 거리는 0
        
            while (!pq.isEmpty()) {
                Node curr = pq.poll();
                if (dist[curr.v] < curr.w) continue;
        
                for (int i = 0; i < adjList[curr.v].size(); i++) {
                    Node next = adjList[curr.v].get(i);
                    if (dist[next.v] > curr.w + next.w) {
                        dist[next.v] = curr.w + next.w;
                        pq.offer(new Node(next.v, dist[next.v]));
                    }
                }
            }
        }
      • 반복문을 이용한 구현

        static class Node {
            int v, w;
            public Node(int v, int w) {
                this.v = v;
                this.w = w;
            }
        }
        
        private static void dijkstra(int start) {
            boolean[] visited = new boolean[V];
        
            dist[start] = 0; // 시작 노드까지의 거리는 0
        
            for (int i = 0; i < V-1; i++) {
                int min = INF;
                int idx = -1;
        
                // 선택하지 않은 정점 중 dist가 가장 짧은 것을 선택
                for (int j = 0; j < V; j++) {
                    if (!visited[j] && min > dist[j]) {
                        min = dist[j];
                        idx = j;
                    }
                }
        
                if (idx == -1) break;
        
                visited[idx] = true; // 선택
        
                // 갱신 가능하다면 생신
                for (int j = 0; j < adjList[idx].size(); j++) {
                    Node curr = adjList[idx].get(j);
        
                    // 방문하지 않았고, 연결도 되었고(인접행렬일 때 해당),
                    // 이미 가지고 있는 값보다 더 낮은 값이 있다면 갱신
                    if (!visited[curr.v] && dist[curr.v] > dist[idx] + curr.w) {
                        dist[curr.v] = dist[idx] + curr.w;
                    }
                }
            }
        }

Floyd-Warshall Algorithm

  1. 기본 점화식

    • Code

      public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
      // 노드의 개수(N), 간선의 개수(M), 거쳐 갈 노드(X), 최종 목적지 노드(K)
      public static int n, m, x, k;
      // 2차원 배열(그래프 표현)를 만들기
      public static int[][] graph = new int[101][101];
      
      public static void main(String[] args) {
          ...
      
          // 최단 거리 테이블을 모두 무한으로 초기화
          for (int i = 0; i < 101; i++) {
              Arrays.fill(graph[i], INF);
          }
      
          // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
          for (int a = 1; a <= n; a++) {
              for (int b = 1; b <= n; b++) {
                  if (a == b) graph[a][b] = 0;
              }
          }
      
         // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
         for (int i = 0; i < m; i++) {
              // A와 B가 서로에게 가는 비용은 1이라고 설정
              int a = sc.nextInt();
              int b = sc.nextInt();
              graph[a][b] = 1;
              graph[b][a] = 1;
          }
      
          x = sc.nextInt();
          k = sc.nextInt();
      
          // 점화식에 따라 플로이드 워셜 알고리즘을 수행
          for (int k = 1; k <= n; k++) {
              for (int a = 1; a <= n; a++) {
                  for (int b = 1; b <= n; b++) {
                      graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                  }
              }
          }
      
          // 수행된 결과를 출력
          int distance = graph[1][k] + graph[k][x];
      
          // 도달할 수 없는 경우, -1을 출력
          if (distance >= INF) {
              System.out.println(-1);
          }
          // 도달할 수 있다면, 최단 거리를 출력
          else {
              System.out.println(distance);
          }
      }
profile
응애 난 애기 개발자

0개의 댓글