[백준 3665] 최종 순위

3665번: 최종 순위

위상정렬로 풀기

5
5 4 3 2 1
2
2 4
3 4

처음 순위 [5,4,3,2,1]대로 단방향 그래프를 생성합니다.

5는 (4,3,2,1)보다 높으므로 5->4, 5->3, 5->2, 5->1 간선을 추가합니다.

4는 (3,2,1)보다 높으므로 4->3, 4->2, 4->1을 추가합니다.

3,2,1도 같은 방식으로 간선을 추가하면

5 -> [4,3,2,1]
4 -> [3,2,1]
3 -> [2.1]
2 -> [1]
1 -> []

여기서 (2, 4)와 (3, 4)의 순위가 바뀝니다. 4->2에서 2->4 로, 그리고 4->3에서 3->4로 순위가 바뀝니다.

5 -> [4,3,2,1]
4 -> [1]
3 -> [4,2.1]
2 -> [4,1]
1 -> []

여기서 위상정렬을 돌려보면

[5,3,2,4,1] 이 됩니다.

하지만 항상 답이 나오지는 않습니다. 지문의 마지막에는 아래와 같이 적혀있습니다.

하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고("?"), 일관성이 없는 잘못된 정보일 수도 있다.("IMPOSSIBLE") 이 두 경우도 모두 찾아내야 한다.

순위를 정할 수 없는 경우를 위상 정렬의 특징과 연관지을 수 있습니다. 위상 정렬을 공부하신 분들은 아시겠지만 위상 정렬은 항상 Indegree가 0인 정점부터 시작합니다. 하지만 이러한 정점이 없으면 더이상 순서를 구할 수 없게 됩니다. 따라서 IMPOSSIBLE이 되는 경우는 Indegree가 0인 정점이 없는 경우, 즉 정렬 후의 데이터의 갯수가 모든 정점의 갯수와 틀리는 경우가 됩니다.

"?"인 경우는 애매모모한 경우 입니다. 위상 정렬은 구현하는 사람의 스타일에 따라 정렬된 순서가 다를 수 있습니다. 하지만 모두 정확한 답이 됩니다. 정렬된 순서가 달라지는 경우는 Indegree가 0인 정점이 2개 이상인 경우 입니다. 전부 동일한 순서이기 때문에 후보 정점들의 순서는 어떻게 되는 상관없기 때문이죠.

하지만 이 문제에서는 명확한 순서를 골라야 합니다. 이 경우는 누가 순위가 높은지 정확히 알 수 없기 때문에 Indegree가 0개인 정점이 두개 이상, 즉 큐 또는 스택에 정점이 2개 이상 남아있는 경우를 "?"로 볼 수 있습니다.

 

정리를 해보면

1. 변경되기 전 순서 대로 그래프를 그린다.
2. 순위가 변경된 정점 사이의 간선의 방향을 바꾼다.
3. 이 상태로 위상 정렬을 수행한다.
4. 중간에 Indegree가 0인 정점이 없으면 IMPOSSIBLE, 2개 이상이 나타나면 ?를 출력한다
5. 정상적으로 정렬을 완료했으면 순위 대로 출력한다.

코드 보기 (Python)

import sys
import collections
input = sys.stdin.readline

OK = 0
IMPOSSIBLE = 1
BAD_REQUEST = 2

def int2result(v):
    if v == OK:
        return True
    elif v == IMPOSSIBLE:
        print("IMPOSSIBLE")
        return False
    else:
        print("?")
        return False

for _ in range(int(input())):
    ans = OK
    n = int(input())
    g = [[0] * (n+1) for _ in range(n+1)]
    parents = [0] * (n+1)
    before = list(map(int, input()[:-1].split()))

    for i in range(n):
        u = before[i]
        parents[u] = i
        for j in range(i+1, n):
            v = before[j]
            g[u][v] = 1

    for _ in range(int(input())):
        a, b = map(int, input()[:-1].split())
        if g[a][b] == 1:
            parents[a] += 1
            parents[b] -= 1
        else:
            parents[a] -= 1
            parents[b] += 1
        g[a][b], g[b][a] = g[b][a], g[a][b]

    # 맨 위에 있는 놈 돌리기
    start = -1
    for i in range(1, n+1):
        if parents[i] == 0:
            if start == -1:
                start = i
            else:
                ans = BAD_REQUEST
                break
    if start == -1:
        ans = IMPOSSIBLE

    if not int2result(ans):
        # 실패
        continue

    # 위상정렬
    q = collections.deque([start])
    res = []
    while q:
        u = q.pop()
        res.append(u)

        for v in range(1, n+1):
            if g[u][v] == 1:
                g[u][v] = 0
                parents[v] -= 1
                if parents[v] == 0:
                    q.appendleft(v)
        if len(q) > 1:
            ans = BAD_REQUEST
            break

    if len(res) < n:
        ans = IMPOSSIBLE
    if int2result(ans):
        print(*res)

위상 정렬 안 쓰고 풀기

등수를 바탕으로 그린 그래프와 위상정렬의 특성을 파악하면 위상정렬 없이도 풀이가 가능합니다. 아까 그렸던 그래프를 다시 한번 봅시다.

5 -> [4,3,2,1]
4 -> [1]
3 -> [4,2.1]
2 -> [4,1]
1 -> []

그래프를 그릴때 간선의 방향이 순위가 낮은 순 이었습니다. 예를 들어 여기에서는 5가 4보다 순위가 높기 때문에 5->4 간선이 존재합니다.

이 그래프를 토대로 Indegree를 구해보면

번호	1	2	3	4	5
Indegree	4	2	1	3	0

이 됩니다.

Indegree가 하나 이상 존재한다는 것은 해당 정점에 상위 순위가 있다는 것이 되고 반대로 하나도 없으면 그 정점은 1등이 됩니다.

예를 들면 5번은 Indgree가 하나도 없으므로 1등, 4는 위에 3개가 있으므로 4등, 3은 위에 1개가 있으므로 2등입니다. 이렇게 Indegree가 적은 순으로 나열해 보면 [5, 3, 2, 4, 1]이 되고 이는 실제 최종 순위가 됩니다.

일반화를 하면 N개의 정점이 있는 유향 그래프가 있을 때, 정점 V의 Indgree가 K면 정점 V의 등수는 K+1등이 됩니다.

하지만 이러한 공식이 성립되려면 각 정점의 Indegree값은 고유해야 하고 Indegree의 값의 범위가 0  ~ N-1이어야 합니다. N이상이 되면 N+1등 이상이 될 텐데 이 등수는 존재하지 않으니까요. 이 경우는 순위를 매길 수 없으므로 IMPOSSIBLE로 처리합니다. 따라서 위상정렬 코드 대신 아래의 코드로 대체합니다.

    res = []
    for i in range(1, n+1):
        # (indegree 갯수, 팀 번호)
        res.append((parents[i], i))
    # indegree가 적은 순으로 정렬 -> 1등 순
    res.sort(key=lambda e: e[0])

    ans = []
    failed = False
    # indegree는 차례대로 0, 1, ... , N-1이어야 한다.
    for i, e in enumerate(res):
        if i != e[0]:
            failed = True
            break
        else:
            ans.append(e[1])
    if failed:
        print("IMPOSSIBLE")
    else:
        print(*ans)

그런데 의문이 생깁니다. "?"가 없습니다. "?"가 나와야 하는 조건은 위상 정렬을 돌릴 때 indegree가 0인 정점이 두개 이상이어서 순위를 만들기가 모호한 경우 입니다. 하지만 여기에서는 이런 케이스가 나오는 경우는 없습니다.

중간에 indegree가 0인 정점이 2개 이상이 나오려면  정점 사이의 간선이 존재하면 안된다는 뜻인데 이 문제에서의 그래프는 각 정점 사이의 순위를 비교해야 하므로 최소 1개 이상은 존재하기 때문입니다. 이해가 안된다면 아래 예제를 봅시다.

예를 들어 순위가 [1,2,3,4]인 케이스가 있습니다. 여기에서 ?가 나오기 위한 최소의 그래프를 그려보면

이런 식으로 2와 3사이를 지나는 간선이 없어야 합니다. 하지만 모든 정점 사이에는 반드시 하나 이상의 간선이 있어야 하기 대문에 이런 식의 그래프는 존재 할 수가 없습니다.

 

정리를 해 보면

1. 변경되기 전 순서 대로 그래프를 그린다.
2. 순위가 변경된 정점 사이의 간선의 방향을 바꾼다.
3. 각 정점의 Indegree를 조사하고, Indgree가 낮은 순으로 정렬한다.
4. 정렬된 요소의 Indegree는 0, 1, ...., N-1순으로 1씩 올라가아한다. 그렇지 않은 경우 IMPOSSIBLE을 출력한다.

코드 보기 (Python)

import sys
import collections
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    g = [[0] * (n+1) for _ in range(n+1)]
    parents = [0] * (n+1)
    before = list(map(int, input()[:-1].split()))

    for i in range(n):
        u = before[i]
        parents[u] = i
        for j in range(i+1, n):
            v = before[j]
            g[u][v] = 1

    for _ in range(int(input())):
        a, b = map(int, input()[:-1].split())
        if g[a][b] == 1:
            parents[a] += 1
            parents[b] -= 1
        else:
            parents[a] -= 1
            parents[b] += 1

    res = []
    for i in range(1, n+1):
        res.append((parents[i], i))
    res.sort(key=lambda e: e[0])

    ans = []
    failed = False
    for i, e in enumerate(res):
        if i != e[0]:
            failed = True
            break
        else:
            ans.append(e[1])
    
    if failed:
        print("IMPOSSIBLE")
    else:
        print(*ans)

마무리

1번은 위상정렬 사용, 2번은 위상정렬을 사용하지 않은 경우 입니다. 2번은 위상정렬을 사용하지 않고 오직 정렬 1번, 선형 탐색 두번 O(2N+NlogN) = O(NlogN)을 진행했기 때문에 위상정렬+인접 그래프를 사용했던 1번O(N^2)보다 성능이 더 빨랐습니다.

위상 정렬을 사용하지 않아도 풀 수 있는 문제 이지만, 위상 정렬과 그래프의 특성을 잘 알고 있어야 위상정렬 없이 풀 수 있는 문제였습니다. 위상 정렬 이론 및 특성을 파악하는데 상당이 도움이 되는 문제라고 생각합니다.