[백준/3665] 최종 순위

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

3665번: 최종 순위

---

 아이디어를 떠올리는 것에 상당히 애를 먹었던 문제일뿐만 아니라, 예외사항에 대해서 모두 고려해야 했던 쉽지 않았던 문제입니다. 다만 후술하겠지만 아이디어를 떠올린 이후에는 구현이 그다지 어렵지 않고, 채점 케이스도 허술하기 때문에.. 어려우면서도 쉬운(?) 문제였던 것 같습니다.

 

풀이

 위상정렬 알고리즘을 사용하는 대표적인 문제로 '선수과목 문제'를 떠올려볼 수 있습니다. 이 문제는 '선수과목 문제'와 상당히 유사하다고 생각했습니다. 순위는 선형적으로만 배치되기 때문에, 1등이 온 후에야 2등, 3등, 4등, 5등이 올 수 있고 2등이 온 후에야 3등, 4등, 5등이 올 수 있고... 이런 식으로 그래프상 연결관계가 표현될 수 있습니다.

 만약 순위가 바뀐다면 간단하게 해당 간선의 방향만 바꾸어주면 됩니다. 예를 들어 2번 팀과 3번 팀의 순위가 바뀌었다고 할 때, 2에서 3으로 연결되는 방향을 3에서 2로 연결되는 역방향으로 바꾸어주면 변경된 그래프를 얻을 수 있습니다. 저는 휴리스틱하게 결과를 얻었는데, 그림을 그려보면 편한 듯 싶습니다.

테스트 케이스 1번의 그래프

 입력 예시의 테스트 케이스 1번을 그래프로 표현하면 위와 같습니다. 후행하는 모든 순위에 대해서 연결해준 모습입니다.

테스트 케이스 1번의 변경된 그래프

2번 노드와 3번 노드, 그리고 3번 노드와 4번 노드의 상대적 순위가 변경되었다고 했으므로 해당하는 두 간선의 방향만 변경해주면 그래프 업데이트가 완료됩니다. 위의 그림에서 빨간색 간선이 방향이 변경된 간선입니다.

 또한 신경써야 하는 것이 '예외 처리'입니다. 문제에서는 '확실한 올해 순위를 만들 수 없는 경우'와 '일관성이 없는 잘못된 정보'인 경우를 찾으라고 정의하였습니다. 위상정렬에서는 주요한 두 가지 오류 케이스가 있습니다.

---

1. 사이클이 발생하는 경우

2. 경우의 수가 다수인 경우

---

 문제에서 제시한 '확실한 올해 순위를 만들 수 없는 경우'가 경우의 수가 다수인 경우에 해당하며, '일관성이 없는 잘못된 정보'인 경우가 사이클이 발생하는 경우라고 볼 수 있습니다. 따라서 두 가지에 주의하며 코드를 작성한다면 무리없이 정답 판정을 받을 수 있습니다. 저같은 경우는 이렇게 체계적으로 알고 있던 건 아니고 그냥 모든 예외에 대해 처리해야겠다는 마인드로 풀었는데, 얼추 비슷하게 접근한 듯 합니다.

 여담으로 실제 백준 사이트의 채점 시스템에는 '?'가 출력되는 케이스가 없습니다. '?'가 출력되는 로직을 아예 빼고 제출해봤는데 만점 판정을 받더군요..

 소스코드는 다음과 같습니다.

from collections import deque


def solution(n, m, array, change):
    # make temporary array
    tmp = []
    for i in range(n):
        for j in range(i + 1, n):
            tmp.append((array[i], array[j]))

    # initialize graph
    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)
    for i, j in tmp:
        graph[i].append(j)
        indegree[j] += 1
        
    for c in change:
        a, b = c
        try:
            graph[a].remove(b)
            graph[b].append(a)
            indegree[b] -= 1
            indegree[a] += 1
        except:
            try:
                graph[b].remove(a)
                graph[a].append(b)
                indegree[a] -= 1
                indegree[b] += 1
            except:
                return '?'

    # topology sort
    q = deque()
    result = []
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)
            result.append(i)

    while q:
        if len(q) >= 2:
            return '?'
        now = q.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                result.append(i)

    if len(result) != n:
        return 'IMPOSSIBLE'
    else:
        return ' '.join(list(map(str, result)))
        
for _ in range(int(input)):
    n = int(input())
    array = list(map(int, input().split()))
    m = int(input())
    change = []
    for _ in range(m):
        change.append(tuple(map(int, input().split())))

    answer = solution(n, m, array, change)
    print(answer)

 저는 미리 solution 함수를 정의하고, 각 테스트 케이스마다 받은 입력을 해당 함수에 인자로 전달하여 결과값을 출력하기로 했습니다. 로직은 크게 4단계로 구성되어 있습니다.

 

1. Temporary array 만들기

# make temporary array
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append((array[i], array[j]))

 array 변수에는 인자로 전달받은 '작년의 순위 정보'가 들어있습니다. 여기서 모든 순위 관계를 추출하여 tmp 리스트 변수에 담았습니다.

 

2. 그래프 초기화

# initialize graph
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for i, j in tmp:
    graph[i].append(j)
    indegree[j] += 1
        
for c in change:
    a, b = c
    try:
        graph[a].remove(b)
        graph[b].append(a)
        indegree[b] -= 1
        indegree[a] += 1
    except:
        try:
            graph[b].remove(a)
            graph[a].append(b)
            indegree[a] -= 1
            indegree[b] += 1
        except:
            return '?'

 앞서 tmp 변수에 담은 순위 정보를 인접 리스트 형태로 받았습니다. 더불어 진입차수(indegree)도 초기화했습니다. 사실 인접 리스트보다 인접 행렬로 받는게 편하긴 했을텐데 아쉬울 따름입니다.

 변화를 반영하는 부분이 사실 핵심이라고 볼 수 있습니다. 순위 변화는 상대적으로 순위가 변화한 두 팀만을 제시하므로, 순서 정보는 전혀 반영하고 있지 않습니다. 즉 2번 팀과 3번 팀의 상대적 순위가 변화했다는 것만 알 수 있을 뿐, 2번 팀이 더 순위가 높은지 3번 팀이 더 순위가 높은지는 그래프를 봐야 알 수 있습니다. 

 따라서 변화가 (a, b)와 같이 주어졌을 때, a에서 b로 연결되어 있는지 b에서 a로 연결되어 있는지 따로 확인하고 로직을 진행시켜야 합니다. 저같은 경우는 인접리스트 방식을 선택했기 때문에 우선 graph[a]에서 b를 빼보기 위해 remove함수를 사용했습니다. remove 함수는 원소가 없을 시 오류를 반환하므로 try ~ except 구문을 사용해서 조건을 분기시켰습니다. 혹시 존재하지 않는 팀이 주어질 수도 있어서 어느 쪽에도 해당하지 않으면 '?'를 반환하도록 해놨습니다만, 아까도 말했듯이 채점 케이스에 '?'가 정답인 경우는 없습니다.. 

 

3. 위상 정렬 수행

# topology sort
q = deque()
result = []
for i in range(1, n + 1):
    if indegree[i] == 0:
        q.append(i)
        result.append(i)

while q:
    if len(q) >= 2:
        return '?'
    now = q.popleft()
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            q.append(i)
            result.append(i)

 일반적인 위상정렬 알고리즘입니다. 여기서 앞선 위상정렬의 오류 케이스 중 '경우의 수가 다수인 경우'에 대한 예외 처리가 들어갑니다. 만약 큐에 두 개 이상의 원소가 한 번에 들어온다면 이는 해당 시점에 고려할 수 있는 경우의 수가 두 개 이상이라는 의미입니다. 따라서 해당하는 경우 '?'를 반환하게 해주었습니다.

 

4. 정답 출력

if len(result) != n:
    return 'IMPOSSIBLE'
else:
    return ' '.join(list(map(str, result)))

 정답을 출력하기 전에 '사이클이 발생하는 경우'에 대한 예외처리도 들어갑니다. 사이클이 발생하는 경우 result의 길이가 원래 팀 개수에 도달하기 전 위상 정렬 알고리즘이 종료될 것입니다. 따라서 result 변수에 들어간 팀의 개수가 원래 팀의 개수와 다른 경우(미만인 경우가 더 좋을 것 같긴 합니다.) 'IMPOSSIBLE'을 반환해줍니다. 그렇지 않은 경우라면 실제 정답을 반환해줍니다.

 위 과정을 매 테스트 케이스마다 새로운 인자를 받아 반복하면 됩니다.

---

추가

 사실 인접행렬을 사용하고, 위상정렬 시 발생하는 오류케이스의 종류에 대해서 미리 알고 있었더라면 더 코드가 간결하고 직관적으로 작성되었을 것입니다. 아래 코드는 인접행렬을 이용하고 위상정렬의 두 가지 오류 케이스에 대해 깔끔하게 처리한 코드입니다.

for tc in range(int(input())):
    n = int(input())
    indegree = [0] * (n + 1)
    graph = [[False] * (n + 1) for i in range(n + 1)]
    
    data = list(map(int, input().split()))
    for i in range(n):
        for j in range(i + 1, n):
            graph[data[i]][data[j]] = True
            indegree[data[j]] += 1
            
    m = int(input())
    for i in range(m):
        a, b = map(int, input().split())
        if graph[a][b]:
            graph[a][b] = False
            graph[b][a] = True
            indegree[a] += 1
            indegree[b] -= 1
        else:
            graph[a][b] = True
            graph[b][a] = False
            indegree[a] -= 1
            indegree[b] += 1
            
    result = []
    q = deque()
    
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)
            
    certain = True
    cycle = False
    
    for i in range(n):
        if len(q) == 0:
            cycle = True
            break
        if len(q) >= 2:
            certain = False
            break
            
        now = q.popleft()
        result.append(now)
        for j in range(1, n + 1):
            if graph[now][j]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    q.append(j)
                    
    if cycle:
        print('IMPOSSIBLE')
    elif not certain:
        print('?')
    else:
        for i in result:
            print(i, end=' ')
        print()