[2단계 위상 정렬] 1203. Sort Items by Groups Respecting ★★★★★

1203. Sort Items by Groups Respecting

 

🔸 문제 설명

There are n items each belonging to zero or one of m groups
→ n개의 아이템이 있으며, 각 아이템은 m개의 그룹 중 하나에 속하거나, 어떤 그룹에도 속하지 않을 수 있습니다.

where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group.
→ group[i]는 i번째 아이템이 속한 그룹 번호이며, 그룹이 없는 경우 -1입니다.

The items and the groups are zero indexed.
→ 아이템과 그룹 번호는 모두 0번부터 시작합니다.

A group can have no item belonging to it.
→ 어떤 그룹에는 아이템이 하나도 없을 수도 있습니다.

Return a sorted list of the items such that:
→ 다음 조건들을 만족하는 아이템들의 정렬된 리스트를 반환하세요:

The items that belong to the same group are next to each other in the sorted list.
→ 같은 그룹에 속한 아이템들은 정렬된 리스트에서 연속적으로 붙어 있어야 합니다.

There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).
→ beforeItems[i]는 i번째 아이템보다 앞에 와야 하는 아이템들의 리스트입니다. 즉, 선행 관계를 나타냅니다.

Return any solution if there is more than one solution and return an empty list if there is no solution.
→ 가능한 정답이 여러 개일 경우 그 중 하나만 반환하면 되고, 정렬이 불가능하면 빈 리스트를 반환하세요.

---

✅ 요약

• beforeItems를 기반으로 **위상 정렬(topological sort)**을 해야 함.
• 조건:
  1. 같은 그룹은 연속적으로 나와야 함
  2. 선행 조건을 만족해야 함
• group[i] == -1인 경우 그룹을 새로 부여해서 고유하게 처리해야 함 (즉, 아이템 자체가 하나의 그룹처럼 다뤄져야 할 수 있음)
• 그룹 간 정렬 + 그룹 내부 정렬 → 2단계 위상 정렬 필요

🔧 문제 해결 전략 (2단계 위상 정렬)

🧠 핵심 아이디어

1. 아이템 간 선행 관계(beforeItems)를 고려해야 한다. → 아이템 단위 위상 정렬
2. 같은 그룹끼리는 서로 붙어 있어야 한다. → 그룹 단위 위상 정렬도 함께 고려해야 한다.
3. 따라서, "그룹 간 위상 정렬" + "그룹 내부 위상 정렬" 을 모두 만족해야 함.

---

🪜 단계별 풀이

✅ Step 1: 그룹 번호 재할당

• 문제에서 group[i] == -1인 아이템은 어떤 그룹에도 속하지 않음
• 이럴 땐, 아이템마다 고유한 그룹 번호를 부여해야 그룹 정렬이 쉬워짐

# 그룹 번호가 없는 아이템(-1)에 대해 새 그룹 ID 부여
new_group_id = m
for i in range(n):
    if group[i] == -1:
        group[i] = new_group_id
        new_group_id += 1

---

✅ Step 2: 두 종류의 그래프 만들기

1. 아이템 간 위상 정렬용 그래프
2. 그룹 간 위상 정렬용 그래프

item_graph = defaultdict(list)   # 아이템 간 그래프
item_indegree = [0] * n          # 아이템의 진입 차수

group_graph = defaultdict(list)  # 그룹 간 그래프
group_indegree = [0] * new_group_id  # 그룹의 진입 차수

• beforeItems[i]를 순회하면서:
  • 아이템 간 관계 추가: before -> i
  • 그룹이 다르면 그룹 간 관계도 추가: group[before] -> group[i]

---

✅ Step 3: 위상 정렬 함수 (공통 함수로)

def topological_sort(graph, indegree, nodes):
    queue = deque([node for node in nodes if indegree[node] == 0])
    res = []
    while queue:
        node = queue.popleft()
        res.append(node)
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)
    return res if len(res) == len(nodes) else []

def topological_sort_dfs(graph, nodes):
    visited = set()     # 방문 완료된 노드
    visiting = set()    # 현재 경로 상의 노드 (DFS 중간 경로)
    result = []         # 위상 정렬 결과 리스트

    def dfs(node):
        if node in visiting:
            return False  # 사이클 발생
        if node in visited:
            return True   # 이미 처리 완료된 노드

        visiting.add(node)
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False  # 하위에서 사이클 발생
        visiting.remove(node)
        visited.add(node)
        result.append(node)
        return True

    for node in nodes:
        if not dfs(node):  # DFS 중 사이클 발견 시
            return []
    return result[::-1]

---

✅ Step 4: 두 번의 위상 정렬 수행

• 아이템 위상 정렬 수행 → 실패 시 [] 반환
• 그룹 위상 정렬 수행 → 실패 시 [] 반환

---

✅ Step 5: 그룹별로 아이템을 모아 출력 순서 만들기

• 아이템 위상 정렬 결과를 group별로 묶고,
• 그룹 위상 정렬 결과에 따라 붙여줌

---

🎯 결과 정리

• 아이템 순서 정렬은 선행 조건을 만족하고
• 그룹 순서는 그룹 간 관계와 그룹별 연속성을 만족함

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # 1. 그룹이 없는 항목(-1)에 대해 새로운 그룹 ID를 부여 (아이템 자체를 그룹처럼 처리하기 위해)
        new_group_id = m
        for i in range(n):
            if group[i] == -1:
                group[i] = new_group_id
                new_group_id += 1

        # 2. 아이템 간 그래프 및 진입차수, 그룹 간 그래프 및 진입차수 초기화
        item_graph = defaultdict(list)     # 아이템 간 선행 관계
        item_indegree = [0] * n

        group_graph = defaultdict(list)    # 그룹 간 선행 관계
        group_indegree = [0] * new_group_id

        # 3. 관계 정보 기반으로 그래프 구성
        for curr in range(n):
            for prev in beforeItems[curr]:
                item_graph[prev].append(curr)
                item_indegree[curr] += 1

                if group[prev] != group[curr]:  # 서로 다른 그룹이면 그룹 간 간선 추가
                    group_graph[group[prev]].append(group[curr])
                    group_indegree[group[curr]] += 1

        # 4. DFS 기반 위상 정렬 함수 정의
        def topological_sort_dfs(graph, nodes):
            visited = set()     # 방문 완료된 노드
            visiting = set()    # 현재 DFS 경로에 있는 노드
            result = []

            def dfs(node):
                if node in visiting:
                    return False  # 사이클 발생
                if node in visited:
                    return True

                visiting.add(node)
                for nei in graph[node]:
                    if not dfs(nei):
                        return False
                visiting.remove(node)
                visited.add(node)
                result.append(node)
                return True

            for node in nodes:
                if node not in visited:
                    if not dfs(node):
                        return []  # 사이클 발생 시 실패
            return result[::-1]  # 후위 순회 결과 뒤집기

        # 5. 아이템과 그룹 각각에 대해 위상 정렬 수행
        item_order = topological_sort_dfs(item_graph, list(range(n)))
        if not item_order:
            return []  # 아이템 위상 정렬 실패 시 종료

        group_order = topological_sort_dfs(group_graph, list(range(new_group_id)))
        if not group_order:
            return []  # 그룹 위상 정렬 실패 시 종료

        # 6. 그룹별로 아이템 묶기
        grouped_items = defaultdict(list)
        for item in item_order:
            grouped_items[group[item]].append(item)

        # 7. 그룹 순서에 따라 아이템 정렬 결과 조합
        result = []
        for g in group_order:
            result.extend(grouped_items[g])  # 같은 그룹 내 아이템은 이미 item_order에 의해 정렬되어 있음
        return result