그래프 DFS(위상정렬)

라면 순서대로 끓이기

위 그림처럼 라면 끓이는 Step들이 정의 되어 있다.

어떻게하면 순서대로 출력 할까?

위상 정렬을 사용하면 된다.

 

스텝 정의

public final class Step {
    private final String name;
    private final ArrayList<Step> nextSteps = new ArrayList<>();

    public Step(final String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public ArrayList<Step> getNextSteps() {
        return nextSteps;
    }

    public void addNext(final Step step) {
        this.nextSteps.add(step);
    }
}

스텝 클래스는 자신이 수행하는 이름과 다음 스텝들을 정의한다.

 

 

그래프 생성

    private static ArrayList<Step> createStepGraph() {
        final Step start = new Step("start: 시작");
        final Step water = new Step("water: 물");
        final Step boil = new Step("boil: 물끓이기");

        final Step noodle = new Step("noodle: 면");
        final Step powder = new Step("powder: 스프");
        final Step powderEtc = new Step("powderEtc: 건더기");

        final Step boilFinish = new Step("boilFinish: 물끓이기 완료");
        final Step eat = new Step("eat: 라면 잡수기");

        final Step chopsticks = new Step("chopsticks: 젓가락 세팅");
        final Step kimchi = new Step("kimchi: 김치 세팅");

        start.addNext(water);

        water.addNext(boil);

        boil.addNext(noodle);
        boil.addNext(powder);
        boil.addNext(powderEtc);

        noodle.addNext(boilFinish);
        powder.addNext(boilFinish);
        powderEtc.addNext(boilFinish);

        boilFinish.addNext(eat);
        chopsticks.addNext(eat);
        kimchi.addNext(eat);

        ArrayList<Step> steps = new ArrayList<>();

        steps.add(start);
        steps.add(water);
        steps.add(boil);
        steps.add(noodle);
        steps.add(powder);
        steps.add(powderEtc);
        steps.add(boilFinish);
        steps.add(eat);
        steps.add(chopsticks);
        steps.add(kimchi);

        return steps;
    }

그래프 생성 : 각각의 스텝들을 만들고 그 다음 스텝은 무엇인지 정의한다

 

 

위성 정렬 실행

    public static void main(String[] args) {
        ArrayList<Step> steps = createStepGraph();
        LinkedList<Step> sortedSteps = sortTopologically(steps);

        for (Step step : sortedSteps) {
            System.out.println(step.getName());
        }

    }

    private static LinkedList<Step> sortTopologically(ArrayList<Step> steps) {
        LinkedList<Step> linkedList = new LinkedList<Step>();
        HashSet<Step> discovered = new HashSet<Step>();
        for (Step step : steps) {
            topologicalSortRecursive(step, discovered, linkedList);
        }

        return linkedList;
    }

    private static void topologicalSortRecursive(Step step, HashSet<Step> discovered, LinkedList<Step> linkedList) {
        if (discovered.contains(step)) {
            return;
        }

        discovered.add(step);

        for (Step nextStep : step.getNextSteps()) {
            if (discovered.contains(nextStep)) {
                continue;
            }

            topologicalSortRecursive(nextStep, discovered, linkedList);
        }

        linkedList.addFirst(step);
    }

위 코드에서 핵심은 각각의 모든 Step들이 위상정렬을 재귀적으로 실행 한다는 것이다.

 ※ 이미 실행한 Step이 있으면 반환(discovered)

그리고 DFS 처럼 자기 자신을 add 하기 전에 다음 스텝을 먼저 add한다