그래프 알고리즘 총정리

이상훈·2024년 8월 2일
알고리즘
0

알고리즘

목록 보기
57/57

유니온 파인드

 유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

중요
find() 메서드에서 아래 코드에 유의하자. 연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되는, 즉 경로 압축을 통헤 find() 연산 속도가 O(1)이 된다.
return arr[x] = find(arr[x]);

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static int[] arr;
    
    // union 연산
    public static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b){
            arr[b]= a;
        }
    }
	
    // find 연산
    public static int find(int x){
        if(arr[x]==x){
            return arr[x];
        }
        else{
            return arr[x] = find(arr[x]);
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());
        int m = Integer.valueOf(st.nextToken());
        
        // 대표 노드를 자기 자신으로 초기화
        arr = new int[n+1];
        for(int i=0; i<=n; i++){
            arr[i] = i;
        }
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.valueOf(st.nextToken());
            int a = Integer.valueOf(st.nextToken());
            int b = Integer.valueOf(st.nextToken());
            if(x==0){
                union(a,b);
            }
            else if(x==1){
                if(find(a)==find(b))
                    bw.write(String.valueOf("YES") +"\n");
                else
                    bw.write(String.valueOf("NO") +"\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

백준 1717 집합 표현하기


최단거리 알고리즘

다익스트라

 다익스트라 알고리즘은 그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단거리를 구하는 알고리즘이다.

특징
모든 엣지의 가중치가 양수여야한다.

플로우
1. 인접 리스트 형태로 그래프와 거리 배열을 초기화한다.
2. 우선순위 큐에 시작 노드를 넣고 초기화한다.
3. 큐에서 노드를 꺼내어 연결된 엣지들 중 최소 값을 갱신한다.
4. 갱신된 노드를 큐에 추가한다.
5. 모든 노드에 대해 최단 거리를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    public static class Edge implements Comparable<Edge>{
        int vertex;
        int value;

        public Edge(int vertex, int value){
            this.vertex = vertex;
            this.value = value;
        }

        @Override
        public int compareTo(Edge edge){
            return this.value-edge.value;
        }
    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.valueOf(st.nextToken());
        int E = Integer.valueOf(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int K = Integer.valueOf(st.nextToken());

        List<List<Edge>> graph = new ArrayList<>();
        int[] dist = new int[V+1];
        for(int i=0; i<=V; i++){
            graph.add(new ArrayList<>());
            dist[i] = Integer.MAX_VALUE;
        }
        dist[K] = 0;

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.valueOf(st.nextToken());
            int v = Integer.valueOf(st.nextToken());
            int w = Integer.valueOf(st.nextToken());
            graph.get(u).add(new Edge(v, w));
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(K, 0));

        while(!pq.isEmpty()){
            Edge now = pq.poll();
            int vertex = now.vertex;
            int value = now.value;

            if(dist[vertex]<value)
                continue;

            for(Edge edge : graph.get(vertex)){
                if(dist[edge.vertex]>value+edge.value){
                    dist[edge.vertex] = value+edge.value;
                    pq.offer(new Edge(edge.vertex, dist[edge.vertex]));
                }
            }
        }

        for(int i=1; i<=V; i++){
            if(dist[i]!=Integer.MAX_VALUE)
                bw.write(String.valueOf(dist[i])+"\n");
            else
                bw.write("INF\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

백준 1753 최단경로


벨만포드

 벨만포드 알고리즘은 그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단거리를 구하는 알고리즘이다.

특징
엣지의 가중치가 음수여도 된다.
전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.

플로우
1. 엣지 리스트의 형태로 그래프와 거리 배열을 초기화한다.
2. 노드의 개수 -1만큼 업데이트를 반복한다.
3. 업데이트 1번은 모든 엣지를 대상으로 아래 조건문을 실시하는 것을 의미한다.
D[Start] != ∞이며 D[End] > D[Start] + W -> D[End] = D[Start] + W
4. 업데이트 1번을 추가로 실시해서 거리 배열에 변화가 있는지 확인한다. 만약 변화가 있다면 음수 사이클이 존재함을 의미한다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    public static class Edge{
        int start;
        int end;
        int value;

        public Edge(int start, int end, int value){
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());

        Long[] dist = new Long[N+1];
        for(int i=0; i<=N; i++){
            dist[i] = Long.MAX_VALUE;
        }
        dist[1] = 0l;
        List<Edge> list = new ArrayList<>();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.valueOf(st.nextToken());
            int e = Integer.valueOf(st.nextToken());
            int v = Integer.valueOf(st.nextToken());
            list.add(new Edge(s, e, v));
        }
        int cnt = 0;
        boolean flag = true;
        while(cnt<N){
            for(int i=0; i<M; i++){
                Edge edge = list.get(i);
                if(dist[edge.start]!=Long.MAX_VALUE && dist[edge.end]>dist[edge.start]+edge.value){
                    dist[edge.end] = dist[edge.start] + edge.value;
                    if(cnt==N-1){
                        flag = false;
                    }
                }
            }
            cnt++;
        }
        if(flag == true){
            for(int i=2; i<=N; i++){
                if(dist[i]==Long.MAX_VALUE)
                    bw.write(String.valueOf(-1)+"\n");
                else
                    bw.write(String.valueOf(dist[i])+"\n");
            }
        }
        else
            bw.write(String.valueOf(-1));

        bw.flush();
        bw.close();
        br.close();
    }
}

백준 11657 타임머신


플로이드 와셜

 플로이드 와셜 알고리즘은 그래프에서 모든 노드간에 최단거리를 구하는 알고리즘이다.

특징
엣지의 가중치가 음수여도 된다.

플로우
플로이드 와셜 알고리즘의 핵심 원리는 s노드에서 e노드까지의 최단 경로를 구했다고 가정했을 때 최단 경로 위에 k노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

  1. 인접 행렬로 최단 거리 배열을 초기화한다.
  2. 3중 for문을 돌려서 배열을 업데이트한다. 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m = Integer.valueOf(st.nextToken());
        final int INF= 1000000000;

        int[][] graph = new int[n+1][n+1];
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                if(i==j)
                    graph[i][j] = 0;
                else
                    graph[i][j] = INF;
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.valueOf(st.nextToken());
            int b = Integer.valueOf(st.nextToken());
            int c = Integer.valueOf(st.nextToken());
            graph[a][b] = Math.min(graph[a][b], c);
        }
		
        // 3중 for문.. 플로이드 와셜의 핵심 부분
        for(int k = 1; k<=n; k++){
            for(int s=1; s<=n; s++){
                for(int e=1; e<=n; e++){
                    graph[s][e] = Math.min(graph[s][e], graph[s][k] + graph[k][e]);
                }
            }
        }
	
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(graph[i][j]==INF)
                    bw.write("0 ");
                else
                    bw.write(graph[i][j] +" ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

백준 11404 플로이드


최소 신장 트리

 최소 신장 트리는 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리다. 최소 신장 트리를 구현하는 방법으로는 크루스칼과 프림이 있다. 여기서는 유니온-파인드 알고리즘을 사용하는 크루스칼에 대해 알아본다.

플로우
1. 인접 리스트가 아닌 엣지 리스트의 형태로 그래프를 초기화하자.
2. 가중치가 낮은 엣지부터 선택하자.
2.1. 만약 선택을 함으로써 싸이클이 형성된다면(Find()를 통해 판단) 해당 간선은 선택하지 않는다.
3. 노드의 개수가 N개일때 엣지의 개수가 N-1이 될 때까지 반복한다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    public static int[] arr;

    public static class Edge implements Comparable<Edge>{
        int s;
        int e;
        int v;

        public Edge(int s, int e, int v){
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge E){
            return this.v - E.v;
        }
    }

    public static int Find(int x){
        if(arr[x]==x){
            return x;
        }
        else{
            return arr[x] = Find(arr[x]);
        }
    }

    public static void Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if(a!=b){
            arr[b] = a;
        }
    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.valueOf(st.nextToken());
        int E = Integer.valueOf(st.nextToken());
        arr = new int[V+1];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for(int i=1; i<=V; i++){
            arr[i] = i;
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.valueOf(st.nextToken());
            int e = Integer.valueOf(st.nextToken());
            int v = Integer.valueOf(st.nextToken());
            pq.offer(new Edge(s, e, v));
        }
        int cnt = 0;
        int result = 0;
        while(cnt<V-1){
            Edge edge = pq.poll();
            int s = edge.s;
            int e = edge.e;
            int v = edge.v;
            if(Find(s)!=Find(e)){
                Union(s, e);
                cnt++;
                result += v;
            }
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

백준 1197 최소 신장 트리 구하기


기타 알고리즘

profile
이상훈
Problem Solving과 기술적 의사결정을 중요시합니다.
이전 포스트

[백준] 17298 : 오큰수

0개의 댓글