DeJa
Techvu
DeJa
전체 방문자
48,644
오늘
4
어제
65
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • 재귀 함수(Recursion Function)
    2021.12.08
    재귀 함수(Recursion Function)

태그

  • JPA
  • java
  • web
  • DATABASE
  • network
  • Spring
  • 알고리즘
  • OS
  • 디자인패턴
  • TDD
  • CS

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

위상 정렬
Algorithms/기본 지식

위상 정렬

2021. 12. 14. 18:04
728x90

위상 정렬(Topology Sort)

위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것이다.

사용 예시

  • 선수과목을 고려한 학습 순서 설정
    • A 과목을 수행하고 B 과목을 수강하는 것을 권장할 때, A, B 를 각각 노드로 표현하고 A -> B 로 가는 방향을 갖는 간선을 그린다.
    • 즉, 그래프 상에서 선, 후 관계가 존재하면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

진입 차수(Indegree)

진입 차수(Indegree)란 특정한 노드로 들어오는 간선의 개수를 의미한다. A -> B, B -> C, D -> B 의 관계를 가질 때 B 에 대한 진입 차수는 2이다.

동작 과정

  • 진입 차수가 0인 노드를 큐에 넣는다.
  • 큐가 빌 때까지 다음의 과정을 반복한다.
    • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

Tip

  • 모든 원소를 방문하기 전 큐가 빈다면 사이클(cycling)이 존재한다고 볼 수 있다.
  • 보통 위상 정렬을 사용하라고 낸 문제들은, 사이클이 발생하지 않는다고 명시하는 경우가 많다.

위상 정렬을 수행한 결과는 큐에서 빠져나간 노드를 순서대로 출력하면 된다. 위 그래프의 결과로는 1-2-5-3-6-4-7 과 1-5-2-3-6-4-7 이 정답이 된다.

구현

public class Main {

    private static int vertexCount; // 노드의 개수
    private static int edgeCount; // 간선의 개수
    private static int[] indegree; // 모든 노드에 대한 진입 차수
    private static List<List<Integer>> graph = new ArrayList<>(); // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
    private static List<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과 리스트

    public static void main(String[] args) {
        input();
        topologySort();
        output();
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        vertexCount = sc.nextInt();
        edgeCount = sc.nextInt();

        indegree = new int[vertexCount + 1];

        // 그래프 초기화
        for (int i = 0; i <= vertexCount; i++) {
            graph.add(new ArrayList<>());
        }

        // 방향 그래프의 모든 간선 정보를 입력 받기
        for (int i = 0; i < edgeCount; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b); // A 노드에서 B 로 이동
            indegree[b] += 1; // 진입 차수 1증가
        }
    }

    private static void topologySort() {
        Queue<Integer> Q = new LinkedList<>();

        // step 0. 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= vertexCount; i++) {
            if (indegree[i] == 0) {
                Q.offer(i);
            }
        }

        // step N. 큐가 빌 때까지 반복
        while(!Q.isEmpty()) {
            // 큐에서 원소 꺼내기
            int now = Q.poll();
            result.add(now);
            // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for (int i = 0; i < graph.get(now).size(); i++) {
                indegree[graph.get(now).get(i)] -= 1;
                // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                if (indegree[graph.get(now).get(i)] == 0) {
                    Q.offer(graph.get(now).get(i));
                }
            }
        }
    }

    private static void output() {
        // 위상 정렬을 수행한 결과 출력
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }
}

위상 정렬의 시간 복잡도는 모든 노드와 간선을 확인한다는 점에서 O(V + E) 이다.

$$O(V + E)$$

References

  • 이것이 코딩 테스트다
728x90
저작자표시 비영리 변경금지
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 기본 지식' 카테고리의 다른 글

부분 집합 구하기(DFS)  (0) 2022.01.03
깊이 우선 탐색(DFS)  (0) 2022.01.03
신장 트리와 크루스칼 알고리즘  (0) 2021.12.13
서로소 집합  (0) 2021.12.12
플로이드 워셜 알고리즘  (0) 2021.12.12
    'Algorithms/기본 지식' 카테고리의 다른 글
    • 부분 집합 구하기(DFS)
    • 깊이 우선 탐색(DFS)
    • 신장 트리와 크루스칼 알고리즘
    • 서로소 집합
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    깊이 우선 탐색(DFS)
    다음 글
    깊이 우선 탐색(DFS)
    신장 트리와 크루스칼 알고리즘
    이전 글
    신장 트리와 크루스칼 알고리즘

    티스토리툴바