[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day6) : 그래프(서로소 집합(Union-Find), 위상정렬(Topological Sort))

카테고리 없음

[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day6) : 그래프(서로소 집합(Union-Find), 위상정렬(Topological Sort))

developer of the night sky 2024. 8. 15. 15:51

그래프 (Graph)

현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것

그래프 표현

1. 간선 리스트(Edge List)

정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 E x 2 (or E x 3) 이차원 배열(A)에 간선 정보를 저장
어떤 두 정점 vi, vj를 연결하는 간선 ek = (vi, vj) 에 대해서 A[k][0] = vi, A[k][1] = vi
가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장
벨만-포드 알고리즘에서 사용한다.

코드 구현

간선 정보 class

static class Edge{
    int from;
    int to;
    int cost;

    public Edge(int from, int to, int cost){
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

인접 리스트 생성

ArrayList<Edge>[] edgeList = new ArrayList[N+1];
// 각 정점별 인접리스트 init
for(int n=0; n<N+1; n++){
    edgeList[n] = new ArrayList<>();
}

int from, to, cost;
for(int m=0; m<M; m++){
    st = new StringTokenizer(br.readLine());
    from = Integer.parseInt(st.nextToken());
    to = Integer.parseInt(st.nextToken());
    cost = Integer.parseInt(st.nextToken());

    edgeList[from].add(new Edge(from, to, cost));
}

2. 인접 행렬(Adjacency Matrix)

정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V x V 이차원 배열(A)에 그래프 정보를 저장
플로이드-워셜 알고리즘에서 사용한다.

코드 구현

int[][] adjMatrix = new int[N+1][N+1];

int from, to, cost;
for(int m=0; m<M; m++){
    st = new StringTokenizer(br.readLine());
    from = Integer.parseInt(st.nextToken());
    to = Integer.parseInt(st.nextToken());
    cost = Integer.parseInt(st.nextToken());

    adjMatrix[from][to] = cost;
}

3. 인접 리스트 (Adjacent List)

정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V개의 연결 리스트로 그래프 정보를 저장
다익스트라 알고리즘에서 사용한다.

코드 구현

간선 정보 class

public static class Edge{
    int node;
    int cost;

    public Edge(int node, int cost){
        this.node = node;
        this.cost = cost;
    }
}

인접 리스트 생성

ArrayList<Edge>[] adjList = new ArrayList[N+1];
// 각 정점별 인접리스트 init
for(int n=0; n<N+1; n++){
    adjList[n] = new ArrayList<>();
}

int from, to, cost;
for(int m=0; m<M; m++){
    st = new StringTokenizer(br.readLine());
    from = Integer.parseInt(st.nextToken());
    to = Integer.parseInt(st.nextToken());
    cost = Integer.parseInt(st.nextToken());

    adjList[from].add(new Edge(to, cost));
}

서로소 집합(Union-Find)

Disjoint Set
교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조
Union 연산
- 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산
- a, b의 부모가 다르면 두 원소는 같은 집합에 속해 있지 않다. a의 부모를 b의 부모로 대입 or b의 부모를 a의 부모로 대입하여 하나로 합친다.
Find 연산
- 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환

코드 구현

- union

private static void union(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);
    if (aRoot != bRoot)
        parent[aRoot] = bRoot;

}

- find

private static int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}

예제문제

https://www.acmicpc.net/problem/1717

백준 1717번 : 집합의 표현

기본적인 union-find 문제이다.

자세한 풀이는 아래 링크를 참고해주세요.

[코테] 백준 1717번 : 집합의 표현 (java)

https://www.acmicpc.net/problem/1717알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find의 기초 문제이다. Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이

steady-record.tistory.com

위상정렬(Topological Sort)

DAG (비순환 방향 그래프)
- 순환을 가지지 않는 방향 그래프
- 일반적으로 우선순위(선행작업 후 후행작업)를 가진 일련의 작업들은 DAG 구조를 가진다.
위상정렬
- DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것
- 일반적으로 위상정렬의 결과는 유일하지 않다.
- 교과 과정 설계, 작업 스케줄링, 컴파일러의 코드 컴파일 순서 등에 활용된다.