[백준 3665 파이썬] 최종 순위 (골드 1, 위상 정렬)

알고리즘 유형 : 위상 정렬
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
from collections import deque
input = sys.stdin.readline

# 위상 정렬
def topologicalSort(n, graph, inDegree, isLinked):
    q = deque()
    res = []
    
    for team in range(1, n+1):
        if inDegree[team] == 0:
            q.append(team)
    
    while q:
        team = q.popleft()
        res.append(team)
        
        for adj_team in graph[team]:
            # 해당 간선이 실제로 연결되어 있는
            # 유효한 간선인지를 isLinked로 판단하여
            # 만약 0이라면 해당 간선은 무시
            if isLinked[team][adj_team] == 0:
                continue
            
            inDegree[adj_team] -= 1
            
            if inDegree[adj_team] == 0:
                q.append(adj_team)
    
    return res
        

T = int(input())

for _ in range(T):
    n = int(input())
    rank_prev = [*map(int, input().split())]
    
    # 단방향 연결 그래프
    graph = [[] for _ in range(n+1)]
    
    # isLinked[a][b]는 a -> b 간선이 실제로
    # 연결이 되어있는 실재하는 간선인지에 대한
    # boolean 값을 의미
    isLinked = [[0]*(n+1) for _ in range(n+1)]
    
    # 진입 차수
    inDegree = [0]*(n+1)
    
    # 작년 순위에 대해, 가능한 모든 단방향 간선을
    # graph애 넣어주고, isLinked와 inDegree 갱신
    for idx1 in range(n-1):
        for idx2 in range(idx1+1, n):
            team1 = rank_prev[idx1]
            team2 = rank_prev[idx2]
            
            graph[team1].append(team2)
            isLinked[team1][team2] = 1
            inDegree[team2] += 1
    
    m = int(input())
    
    for _ in range(m):
        team_a, team_b = map(int, input().split())
        
        # 어떤 두 노드는 반드시 단방향 간선을 가지고 있음
        # 따라서 조건문을 a -> b인 경우, b -> a 인 경우 총
        # 두 갈래로 분기
        if isLinked[team_a][team_b]:
            # 만약 a와 b가 a -> b 간선으로 연결된 경우,
            # 상대적 순위 변동을 반영하기 위해
            # 반대 방향으로 간선을 넣어주고,
            # 원래의 방향의 isLinked는 false로 바꿔주고
            # inDegree는 1 감소시켜주고, 바꾼 방향에
            # 대한 isLinked는 1로, inDegree는 1 더해준다.
            # 이렇게 되면 원래 a -> b 방향의 간선은
            # isLinked와 inDegree에서 없애주는 작업을 처리
            # 해줬지만 graph 리스트에는 정보가 남아있게
            # 되는데, 이는 위상 정렬 함수 내부에서 
            # isLinked의 값으로 유효 간선 여부를 판단하여
            # 걸러낼 수 있음.
            graph[team_b].append(team_a)
            isLinked[team_a][team_b] = 0
            isLinked[team_b][team_a] = 1
            inDegree[team_b] -= 1
            inDegree[team_a] += 1
        elif isLinked[team_b][team_a]:
            graph[team_a].append(team_b)
            isLinked[team_b][team_a] = 0
            isLinked[team_a][team_b] = 1
            inDegree[team_a] -= 1
            inDegree[team_b] += 1
    
    res = topologicalSort(n, graph, inDegree, isLinked)
    
    # 사이클이 존재하는 경우 순위를 확정지을 수 없으므로
    # IMPOSSIBLE 출력. 다만 유의할 점이 있는데,
    # 작년 순위가 1, 2, 3, 4로 주어졌다고 치고,
    # 상대적 변동이 2 3, 3 4로 주어졌다고 치면,
    # 1팀의 진입차수가 0이지만 그래프에는 2-3-4 사이클이
    # 존재하는 상태이다. 따라서 위상 정렬 내부에서는 1을
    # 현재 순위 리스트에 넣은 다음, 2 3 4 중에서 진입 차수
    # 가 0인 것이 없으므로 그대로 종료한다.
    # 즉 이 경우에는 사이클이 있더라도 res의 길이가 1이 되는
    # 케이스이므로, 이런 경우까지 고려하여 IMPOSSIBLE을 출력하는
    # 조건으로 len(res) < n을 작성해준 것이다.
    # 참고로, 문제에서 설명하는 "?"의 경우는 존재하지 않는다.
    # 이미 작년의 순위를 제공한 순간, 모든 노드 사이의 단방향
    # 간선이 존재하기 때문이다.
    if len(res) < n:
        print("IMPOSSIBLE")
    else:
        print(*res, sep=" ")

풀이 요약

1. 간선을 직접 만들어 놓고, 조건에 따라 일부 간선의 방향을 뒤바꾼 후, 그것으로 위상 정렬을 하는 문제이다.

2. 간선을 만든다는 것은 다음을 의미한다.

   만약 [1, 2, 3, 4]가 작년의 순위였다고 하자.

   그러면 이를 만족하는 모든 가능한 단방향 간선은

   1->2
   1->3
   1->4
   2->3
   2->4
   3->4

   이다.

   이 것을 2차원 리스트로 나타내면 된다.

   다만 이 문제에서는 기존의 위상 정렬과 달리, 추가적으로 isLinked 리스트를 선언해준다.

   이 리스트는 2차원 리스트로, isLinked[a][b]는 a -> b 간선이 실제로 유효한 간선인지를 나타내는 값이다.

   만약 graph[a]에 b가 들어있다고 해도, isLinked[a][b]가 0이라면 이 간선은 실제로는 없는 간선인 것이다.

   이 것을 판단하여 걸러주는 부분은 위상 정렬 함수 내에 조건문으로 있다.

   while q:
         team = q.popleft()
         res.append(team)
         
         for adj_team in graph[team]:
             # 해당 간선이 실제로 연결되어 있는
             # 유효한 간선인지를 isLinked로 판단하여
             # 만약 0이라면 해당 간선은 무시
             if isLinked[team][adj_team] == 0:
                 continue
             
             inDegree[adj_team] -= 1
             
             if inDegree[adj_team] == 0:
                 q.append(adj_team)

3. 이제 상대 순위가 변동한 팀의 간선을 업데이트해주자.

   만약 a b로 주어졌다면, a와 b의 상대 순위가 변동된 것이다.

   원래의 순위는 a -> b 또는 b -> a 둘 중 하나다. 이는 isLinked로 판단해주자.

   if의 실행문 안에서, 우선 그래프에 간선 정보를 넣어준다(graph[b].append(a))

   이 때, 원래의 간선(graph[a]에 들어있는 b)이 남아있게 되는데, 이 간선은 위상 정렬 함수 내부에서 isLinked[a][b]가 0이면 무시해주도록 조건문을 작성하면 된다.

   이 후 isLinked를 업뎃해주자. 원래의 간선은 0으로, 변동된 간선은 1로.

   inDegree도 원래 간선은 1 빼주고, 업뎃 간선은 1 더해주자.

4. 이제 위상 정렬을 수행하면 된다.

   이 때, 그래프에 사이클이 있는 경우에는 순위를 특정지을 수 없으므로 IMPOSSIBLE을 출력해야 된다.

   그런데 유의할 점은, 사이클이 있을 때 모든 노드의 진입 차수가 1 이상이라고 착각하는 경우다.

   사이클이 있고 모든 노드의 진입 차수가 1인 경우에는, 위상 정렬 함수 내에서 큐에 아무 것도 안들어가므로 while문을 진입하지 않기에 위상 정렬 리턴 값인 res는 빈 리스트이다.

   따라서 결과를 출력할 때 res의 길이가 0일 때 IMPOSSIBLE, 아닐 때 res를 출력해버리게 될 것이다.

   그러나 사이클이 있더라도 진입 차수가 1 이상인 노드가 있어 위상 정렬의 리턴 값 res에 어떤 원소가 들어가는 경우도 존재한다.

   예를 들어, 작년 순위가 [1, 2, 3, 4]로 주어졌고, 변동 순위가

   2 3
   3 4

   이렇게 주어졌다고 치자.

   이 때 2-3-4 사이클이 발생하지만, 1의 진입 차수가 0이다.

   따라서 위상 정렬 함수를 거치면 res 리스트에 1이 들어간채로 리턴이 되므로,

   res의 길이가 1이 된다.

   즉, 결과 출력할 때 조건문 분기를 res의 길이가 n 미만이냐 아니냐로 분기해야 모든 케이스를 고려한 풀이이다.

   참고로, 문제에서 "?"로 출력하는 경우는 존재하지 않는다.

   "?"가 출력되기 위해서는 복수의 순위가 나오는 경우여야 하는데(사이클이 있는 경우와는 다름. 사이클이 있을 때는 아예 모든 경우가 답이 될 수 없음), 작년 순위가 주어진 시점에서 이미 모든 노드 사이의 단방향 간선이 존재하기 때문에 이 경우는 애초에 불가능하다.

배운 점, 어려웠던 점

• "?"이 출력되는 경우가 도대체 뭐가 있는지를 생각하느라 시간을 많이 썼다.. 아무리 생각해도 없는데, 없는게 맞다니... 통수 씨게 맞았네ㅠ

• 처음에 len(res) == 0으로 조건을 분기해서 답을 출력했다가 50%에서 계속 WA가 떠서 당황했다.

  아니 len(res)가 1 초과 n 미만인 케이스가 있다고?

  결국 다른 사람 풀이를 참고해봤는데 len(res)가 n 미만인 경우는 모조리 IMPOSSIBLE로 출력하더라..

  그 이유는 나와있지 않아서 그냥 무지성으로 계속 생각해보다가 결국 해당 케이스를 알아낸 것이다.

  WA를 내는 예외적인 테스트 케이스를 생각해내는게 참 어려운 것 같다... 이 부분도 많이 연습해두자.