문제 #35057

Question

톱사상 T를 일으키는 컷셋에 해당하는 것은?

Accepted Answer

톱사상(Topological Sort)은 방향 비순환 그래프(DAG)에서 노드들의 선형 순서를 결정하는 것입니다. "톱사상 T를 일으키는 컷셋"이라는 표현은 문맥상 그래프의 특정 부분 집합이 톱사상을 불가능하게 만드는 경우를 의미하는 것으로 보입니다. 톱사상은 순환이 존재하면 불가능하므로, 컷셋은 그래프에서 제거했을 때 순환을 없애는 간선들의 집합을 의미합니다. 문제의 보기들이 노드들의 집합으로 주어졌다는 점, 그리고 정답이 3번 "{A, B, C}"라는 점을 고려할 때, 이 문제는 그래프에 A, B, C 세 노드가 특정 순서로 연결되어 순환을 형성하고 있으며, 이 세 노드를 모두 포함하는 컷셋이 톱사상을 불가능하게 만든다는 것을 시사합니다. 즉, A -> B -> C -> A 와 같은 순환 구조가 존재할 때, 이 세 노드를 모두 제거해야만 순환이 사라지고 톱사상이 가능해집니다.

문제 1