Problem Session 6 -1부

10분만이라도 하자

안녕하세요, 코드 아키텍트입니다. 오늘은 위상 정렬 문제를 풀어보겠습니다. 하루에 10분이라도 시간을 내어 꾸준히 글을 쓰고자 합니다. 완벽하지 않을 수 있지만, 그래도 해보겠습니다.

문제 설명

음 문제가 이렇습니다. 위상정렬(Topological Sort)에 대해 다루는 이야기입니다. 문제에서 하라는 것은 이렇습니다.

주어진 방향 그래프(Directed Graph) G에 대해 다음 질문에 답하십시오:  

(a) G의 위상 정렬을 제시하고, G의 서로 다른 위상 정렬의 수를 정당화하십시오.

(b) G에 단일 방향 간선을 추가하여 위상 정렬이 불가능한 단순 그래프를 구성하는 간선을 제시하고, 그러한 간선의 수를 정당화하십시오.

자 그럼 GPT와 함께하는 문제 풀이 시작하겠습니다.

왜 혼자 안 풀어?

핑계 없는 무덤은 없습니다. 사실 제가 알기론 이 과제는 혼자 하는 게 아니고 팀을 이뤄서 하는 것으로 알고 있습니다. 제가 완벽하게 알고 있다면 혼자 풀겠지만, 쉽지 않네요. 그래서 훌륭한 선생에게 문답하며 문제를 풀어보았습니다. 참고로 해설은 사이트에 가면 있습니다. 그러므로 GPT와 한 내용은 어쩌면 틀릴지도 모릅니다. 그래도 일단 풀어보는 연습이라 생각하고 적습니다.

위상정렬은 DFS

위상 정렬은 DFS(깊이 우선 탐색)를 통해 구할 수 있습니다. DFS를 실행한 후 역순으로 노드를 나열하면 위상 정렬을 얻을 수 있습니다. 어떤 노드를 최초 노드로 선택할지 막막할 수 있습니다. 이 문제를 해결하는 흐름을 GPT가 알려주었습니다.

1. Degree를 파악해야 한다.

위 문제에서 우리 사람 눈에는 얼핏 최초 노드로 쓸만한 애들이 보입니다. 왠지 모르게 5는 안될 거 같습니다. 이유는 이 노드가 바깥을 가리키는 게 없기 때문입니다. 직관은 그런데, 그럼 정말 시작 노드가 되려면 어떤 것을 골라야 할까요? 바로 indegree를 구해야 합니다.

먼저 각 노드의 in-degree(들어오는 간선 수)를 계산해야 합니다. in-degree가 0인 노드가 최초 노드가 됩니다. 예를 들어, 다음과 같습니다:

0: 1 (노드: 2)

1: 2 (노드: 2, 4)

2: 1 (노드: 4)

3: 1 (노드: 0)

4: 0

5: 1 (노드: 0)

이렇게 됩니다. in-degree가 0인 노드는 4입니다. 따라서 4를 기준으로 DFS를 실행합니다.

2번은 다음글에 이어서... 부족한 글이지만 읽어주신 독자분들께 항상 감사합니다.