알고리즘 학습 - (위상정렬)

황제연·2024년 4월 9일

TopologicalSort 동빈나 알고리즘 위상정렬 자바

알고리즘

목록 보기

33/169

코딩테스트 대비 알고리즘 개념 학습 및 알고리즘 구현 후, 정리하기 위해 작성하는 글입니다

위상정렬 (Topological Sort)

위상정렬은 그래프와 관련된 알고리즘이다.
위상정렬은 순서가 정해져 있는 작업을 순서대로 수행해야할 때,
그 순서를 정해주기 위해 사용하는 알고리즘이다

위와 같이 순서가 정해져 있다고 했을 때,
대학생이 되기는 먼저 행해야할 순서가 없기 때문에 바로 시작할 수 있다.
이어서 4학년 되기와 학과 사이트 가입하기 모두 대학생되기가 완료되었기에 가능하다

하지만 졸업시험 신청하기는 자격서류 제출하기위 학과 사이트 가입하기를 모두 만족해야지 진행이 가능하다. 따라서 순서대로 진행한다면 다음과 같은 결과가 나올 것이다

대학생 되기 -> 4학년 되기 -> 학과 사이트 가입하기 -> 정보처리기사 합격하기
-> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기

이러한 유형의 문제를 프로그래밍 세계에서 해결해주는 것이 바로 위상정렬이다

위상정렬 주의점

위상정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다
즉, 사이클이 발생하지 않지 않는 방향 그래프에서만 가능하며
다시 말하면 사이클이 발생하면 위상정렬을 수행할 수 없다

만약 이전 과정이 위와 같이 되어있었다면 위상정렬은 불가능했을 것이다.
애초에 시작점부터 찾지 못하기 때문이다

위상정렬 구현

위상정렬 알고리즘 구현방법에는 다양한 방법이 있으나 가장 대표적인 방법은 큐를 활용하는 것이다

준비사항

먼저 위상정렬이 가능한 그래프가 방향 그래프가 존재해야한다
그리고 각 노드별 진입차수를 담은 배열이 필요하다

진행 순서

먼저 진입차수가 0인 노드를 큐에 삽입한다
이어서 큐가 비어있지 않은 동안 탐색을 반복한다
큐에서 하나를 꺼내어서 해당 큐와 연결된 모든 노드를 확인한다
이때 해당 노드들의 진입차수를 1씩 감소시키고, 0이 되는지 확인한다
만약 0이라면 큐에 넣고 이전 과정을 반복한다

구현 코드

위 준비사항와 진행순서를 토대로 만든 자바 코드이다.

import java.io.*;
import java.util.*;



public class Main {

    // 임시 그래프
    static List<Integer>[] node = new ArrayList[9];

    // 그래프 노드 별, 진입차수
    static int[] edge = new int[9];
    static void topologicalSort(){
        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i < edge.length; i++) {
            if(edge[i] == 0){
                q.offer(i);
            }
        }

        while(!q.isEmpty()){
            int now = q.poll();
            sb.append(now +" ");
            List<Integer> list = node[now];
            for (int i = 0; i < list.size(); i++) {
                edge[list.get(i)]--;
                if(edge[list.get(i)] == 0){
                    q.offer(list.get(i));
                }
            }
        }

    }

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < 9; i++) {
            node[i] = new ArrayList<>();
        }

        // 그래프 각 노드별 인접한 노드정보 초기화
        node[1].add(2);
        node[1].add(4);
        node[2].add(5);
        node[2].add(6);
        node[3].add(6);
        node[4].add(2);
        node[4].add(8);
        node[7].add(3);
        node[8].add(6);

        // 진입차수 테이블 초기화
        edge[2] = 2;
        edge[3] = 1;
        edge[4] = 1;
        edge[5] = 1;
        edge[6] = 3;
        edge[8] = 1;
        topologicalSort();

        bw.write(sb.toString()+"");

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

}