백준 3665번: 최종 순위 - 위상 정렬로 순위 결정하기

https://www.acmicpc.net/problem/3665

📌 문제 개요

ACM-ICPC 대회에서 작년 순위와 올해 변경된 팀 쌍만 주어졌을 때, 올해의 최종 순위를 결정하는 문제입니다.

핵심 요구사항:

• 작년 완전한 순위가 주어짐
• 올해는 순위가 바뀐 팀 쌍만 제공
• 가능한 결과: 유일한 순위 / 불확실한 순위(?) / 모순(IMPOSSIBLE)

🎯 위상 정렬(Topological Sort)이란?

개념 정의

위상 정렬은 방향 그래프에서 모든 방향 간선의 순서를 지키면서 정점들을 나열하는 방법입니다.

간단히 말해, A → B 간선이 있다면 결과에서 A가 B보다 앞에 나와야 합니다.

실생활 예시

대학 수강 신청을 생각해보세요:

프로그래밍기초 → 자료구조 → 알고리즘
                ↘ 데이터베이스

위상 정렬 결과: 프로그래밍기초 → 자료구조 → 데이터베이스/알고리즘

이 문제에서 위상 정렬이 필요한 이유

1. 순위는 선후 관계다: 1등은 2등보다 앞서고, 2등은 3등보다 앞섭니다
2. 모순 검출 가능: 사이클이 있으면 순위 결정 불가능 (A > B > C > A는 모순)
3. 유일성 검증: 위상 정렬 과정에서 순위가 유일한지 확인 가능

🔍 문제 분석

그래프로 순위 표현하기

• 노드: 각 팀
• 간선: A → B는 "A팀이 B팀보다 순위가 높다"
• 전체 순위: 그래프의 위상 정렬 결과

알고리즘 흐름

1. 작년 순위로 완전 그래프 생성 (모든 팀 간 순위 관계 설정)
2. 변경된 팀 쌍의 간선 방향 뒤집기
3. 위상 정렬로 올해 순위 결정
4. 과정 중 문제 발생 시 적절한 메시지 출력

💻 코드 구현

from collections import deque

def solve():
    n = int(input())
    last_year = list(map(int, input().split()))

    # 인접 행렬 초기화 (adj[i][j] = True: i가 j보다 순위 높음)
    adj = [[False] * (n + 1) for _ in range(n + 1)]

    # 작년 순위를 바탕으로 그래프 구성
    # 순위가 높은 팀에서 낮은 팀으로 간선 생성
    for i in range(n):
        for j in range(i + 1, n):
            adj[last_year[i]][last_year[j]] = True

    # 상대 순위가 바뀐 팀들의 간선 뒤집기
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())
        # a와 b의 간선 방향을 뒤집음 (스왑)
        adj[a][b], adj[b][a] = adj[b][a], adj[a][b]

    # 진입 차수 계산
    indegree = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if adj[i][j]:
                indegree[j] += 1

    # 위상 정렬 시작
    queue = deque()
    result = []

    # 진입 차수가 0인 노드를 큐에 추가
    for i in range(1, n + 1):
        if indegree[i] == 0:
            queue.append(i)

    certain = True  # 순위가 확실한지 여부
    cycle = False   # 사이클 존재 여부

    # n개의 노드를 모두 방문
    for _ in range(n):
        if len(queue) == 0:
            # 큐가 비었으면 사이클 존재
            cycle = True
            break

        if len(queue) >= 2:
            # 큐에 2개 이상이면 순위가 확실하지 않음
            certain = False

        # 큐에서 노드 하나 꺼내기
        curr = queue.popleft()
        result.append(curr)

        # 연결된 노드들의 진입 차수 감소
        for next_node in range(1, n + 1):
            if adj[curr][next_node]:
                indegree[next_node] -= 1
                if indegree[next_node] == 0:
                    queue.append(next_node)

    # 결과 출력
    if cycle:
        print("IMPOSSIBLE")
    elif not certain:
        print("?")
    else:
        print(*result)

# 테스트 케이스 처리
t = int(input())
for _ in range(t):
    solve()

📊 예제 상세 분석

예제 1번 케이스

입력:

• 작년 순위: 5 4 3 2 1
• 변경: (2,4), (3,4)

초기 그래프 구성:

5 → 4, 5 → 3, 5 → 2, 5 → 1
4 → 3, 4 → 2, 4 → 1
3 → 2, 3 → 1
2 → 1

간선 뒤집기 후:

5 → 4, 5 → 3, 5 → 2, 5 → 1
2 → 4 (변경됨!)
3 → 4 (변경됨!)
3 → 2, 3 → 1
2 → 1

위상 정렬 과정:

단계	진입차수 0인 노드	선택	결과 배열
1	5	5	[5]
2	3	3	[5, 3]
3	2	2	[5, 3, 2]
4	4	4	[5, 3, 2, 4]
5	1	1	[5, 3, 2, 4, 1]

결과: 5 3 2 4 1 ✅

🎯 세 가지 결과 케이스

1. 유일한 순위 결정 가능

• 각 단계에서 진입차수 0인 노드가 정확히 1개
• 모든 팀을 순서대로 나열 가능
• 정상적으로 순위 출력

2. 순위 불확실 ("?")

• 어느 시점에 진입차수 0인 노드가 2개 이상
• 예: A와 B 모두 진입차수 0 → A-B 또는 B-A 둘 다 가능
• 순위가 유일하지 않음

3. 모순 발생 ("IMPOSSIBLE")

• 그래프에 사이클 존재
• 예: A → B → C → A (A가 C보다 높으면서 동시에 낮음)
• 위상 정렬 중 진입차수 0인 노드가 없어짐

🔑 핵심 포인트

1. 인접 행렬 사용 이유

• n ≤ 500이므로 O(n²) 공간 복잡도 허용
• 간선 뒤집기가 O(1)로 간단함

2. 간선 뒤집기 구현

adj[a][b], adj[b][a] = adj[b][a], adj[a][b]

Python의 동시 할당으로 깔끔하게 처리

3. Kahn's Algorithm 활용

• 진입 차수 기반 위상 정렬
• 큐를 사용한 BFS 방식
• 사이클과 유일성 검증이 용이

4. 시간 복잡도

• 그래프 구성: O(n²)
• 간선 뒤집기: O(m)
• 위상 정렬: O(n²)
• 전체: O(n² + m)
  
  

참고할 사이트

https://storyofvector7.tistory.com/61

[백준 3665] 최종 순위