[백준/파이썬] 1432번: 그래프 수정 핵심 정리

문제 보기: https://www.acmicpc.net/problem/1432

 

문제 이해하기

예제 입력이 예제 출력으로 이어지는 과정

이 문제에서는 N개의 정점으로 이루어진 그래프에서 모든 간선이 V₁ -> V₂ 형태로 주어질 때, 모든 간선이 V₁ < V₂ 조건을 만족하도록 각 정점에 번호를 새롭게 부여한 뒤, 새로 정해진 번호들의 결과 수열을 출력해야 하는데요. 만약 여러 개의 답이 존재한다면 사전 순으로 가장 앞선 것을 출력합니다.

 

먼저, 문제의 조건을 만족하는 번호를 각 노드에 부여할 때 쉽게 떠오르는 아이디어는 간단한데요. 조건을 위반하는 간선이 있다면, 그 간선이 연결하는 두 노드의 번호를 서로 교환하면 된다는 생각을 할 수 있습니다.

 

하지만 이 접근 방식에는 근본적인 문제가 존재합니다. 특정 간선이 조건을 위반할 때 단순히 두 노드의 번호만 서로 교환하면 당장 해당 간선은 조건을 만족하게 되지만, 교환된 두 노드에 연결된 다른 간선들이 또다시 조건을 위반할 수 있기 때문입니다. 즉, 노드를 단순히 서로 교환하는 방법은 다른 간선에 연쇄적으로 영향을 주어 반복적인 수정이 계속 필요해지는 상황이 발생할 수 있습니다.

 

사실, 현재의 그래프가 당장 잘못된 간선을 가지고 있는지 여부는 그다지 중요하지 않습니다. 모든 간선이 조건을 만족하도록 '모든 노드에 새로운 번호를 부여'하면 되기 때문입니다. 따라서 기존 노드의 숫자를 결과 수열의 인덱스로 생각하면 더욱 이해하기 쉽습니다. 이를 위해 그래프에 위상 정렬을 수행한 다음, 정렬된 순서에 따라 각 노드에 새롭게 번호를 부여하면 됩니다.

 

이를 예시를 통해 좀 더 구체적으로 살펴보겠습니다.

 

위의 그림은 문제의 예제 입력1에 대한 인접 행렬을 그래프로 나타낸 것입니다. 해당 그래프에서 위상 정렬을 수행하면 [ 1, 2, 4, 5, 3 ]이라는 수열을 얻게 되는데요. 이 수열은 각 노드에 새롭게 번호를 부여할 순서를 나타냅니다. 즉, 이 수열의 각 인덱스에 1부터 시작하여 차례대로 번호를 부여하면 되는 것이죠. 구체적으로, 1번 인덱스에 1, 2번 인덱스에 2, 4번 인덱스에 3, 5번 인덱스에 4, 마지막으로 3번 인덱스에 5를 부여하면 됩니다.

 

그러면 최종적으로 [ 1, 2, 5, 3, 4 ]라는 결과 수열을 얻게 되며, 이 결과 수열을 기반으로 수정한 그래프는 위 그림과 같습니다. 결과적으로 모든 간선이 V₁ < V₂인 조건을 만족하게 되었고, 이 결과 수열은 예제 출력 1과 정확히 일치함을 확인할 수 있습니다.

 

하지만 위상정렬은 동일한 차수를 가진 노드가 여러 개일 때 여러 개의 유효한 결과를 만들 수 있습니다.

 

위의 그림을 살펴보면 [ 2, 1, 5, 3, 4 ]라는 또 다른 결과 수열도 모든 간선에 대한 조건을 만족합니다. 따라서 문제에서는 이처럼 여러 답이 가능한 경우 사전 순 가장 앞서는 결과를 유일한 정답으로 간주합니다. 이러한 이유로 예제 출력 1에서는 [ 1, 2, 5, 3, 4 ]가 최종 정답이 됩니다.

 

 

기존 Indegree 기반 위상 정렬의 한계

그렇다면 사전 순으로 가장 앞서는 수열을 얻으려면 어떻게 해야 할까요? 예를 들어, 노드의 수가 5개라면 사전 순으로 가장 앞서는 수열은 [ 1, 2, 3, 4, 5 ]일 것입니다. 그리고 이 수열과 가장 가까운 형태의 결과 수열이 정답이 되겠죠. 즉, 낮은 인덱스에 낮은 숫자를, 높은 인덱스에는 높은 숫자를 부여해야 사전 순으로 가장 앞서는 결과를 얻을 수 있습니다.

 

이를 위해 동일한 차수를 가진 여러 인덱스가 있다면, 최소 힙(min-heap)을 이용해 항상 가장 작은 인덱스를 우선 선택해 더 작은 번호를 부여함으로써 사전 순으로 가장 앞선 수열을 얻을 수 있지 않을까요? 이번엔 다른 예제를 통해 이 방식을 구체적으로 확인해보겠습니다.

 

위의 그림은 임의의 입력에 대한 인접 행렬을 그래프로 나타낸 것입니다. 이 그래프에서 위상 정렬을 수행하면, 먼저 1번 인덱스가 처리된 뒤 동일한 차수를 가지는 3번과 4번 인덱스가 후보로 올라옵니다. 우리는 최소 힙을 사용하고 있으므로 더 작은 인덱스인 3번을 우선 처리합니다. 그 뒤에는 4번, 2번, 5번 인덱스 순서로 처리되겠죠. 따라서 위상정렬 결과로 [ 1, 3, 4, 2, 5 ]라는 수열을 얻게 됩니다.

 

이 결과를 토대로 번호를 부여하면 위 그림과 같은 [ 1, 4, 2, 3, 5 ]라는 결과 수열이 만들어집니다. 그렇다면 이 결과 수열은 예제 입력 1에서처럼 정답이 될 수 있을까요?

 

안타깝게도 위 그래프에서 정답으로 인정되는 결과 수열은 위 그림에 나타난 [ 1, 3, 4, 2, 5 ] 뿐입니다. 이 결과 수열 또한 모든 간선에 대한 조건을 만족하며, 동시에 사전 순으로 더 앞서기 때문에 유일한 정답이 됩니다. 하지만 이상하게도, 우리가 최소 힙을 이용하여 정상적으로 위상 정렬을 진행했음에도 불구하고 이러한 결과를 얻지 못했습니다. 이런 상황이 왜 발생했을까요? 그리고 이를 어떻게 해결해야 할까요?

 

위 그림처럼 위상 정렬을 수행하면서 동시에 결과 수열의 각 인덱스에 숫자를 부여한다고 가정해 봅시다. 이때 먼저 처리되는 인덱스에 낮은 숫자를 부여하고, 순서대로 숫자를 늘려가면서 간선 조건을 만족하는 그래프를 만듭니다. 예를 들어 2번, 5번, 3번 인덱스가 먼저 처리되어 각각 숫자 1, 2, 3을 부여받았다고 가정해 보겠습니다.

 

그런데 만약 이 과정에서 이제까지 처리된 인덱스보다 더 작은 인덱스를 뒤늦게 처리하게 된다면 어떨까요? 위 상황과 같이 1번 인덱스가 늦게 처리되어 숫자 4를 받게 된다면, 이미 처리된 인덱스들보다 더 큰 숫자가 더 작은 인덱스에 부여되는 문제가 발생합니다. 사전 순으로 가장 앞서는 결과 수열을 얻기 위해서는 낮은 인덱스에 낮은 수를 배치해야 하지만, 현재 상황은 오히려 그 반대입니다. 결과적으로 사전 순에서 더욱 멀어진 형태가 되어 버리는 것입니다. 즉, 단순히 증가하는 순서로 숫자를 부여할 때 이런 문제가 발생하게 됩니다.

 

 

 

핵심 아이디어

그렇다면 이제 이 문제를 어떻게 해결해야 할지 다시 생각해 봅시다. 문제의 핵심은 숫자를 증가하는 순서로 부여했기 때문에 발생했습니다. 그러면 오히려 감소하는 순서로 숫자를 부여하면 이 문제를 해결할 수 있지 않을까요? 하지만 현재의 간선 방향대로 위상 정렬을 진행하며 숫자를 감소시키게 되면 V₁ > V₂가 되어 간선 조건을 만족하지 못하게 됩니다. 그러면 이 접근법은 잘못된 걸까요?

 

여기서 한 번 더 생각해 볼 수 있습니다. 숫자를 부여하는 순서를 반대로 했을 때 간선의 방향 때문에 문제가 생긴다면, 간선의 방향 역시 반대로 바꿔주면 어떨까요? 간선의 방향을 바꾸는 게 가능할까 의문을 가질 수도 있지만, 결국 우리가 원하는 조건은 모든 간선이 V₁ < V₂를 만족하는 것입니다. 따라서 간선의 방향을 반대로 바꾸더라도 이 조건을 만족하는 그래프만 구성된다면 아무 문제가 없습니다. 즉, 간선 방향을 모두 반대로 뒤집으면 기존의 indegree 기반 정렬 방식은 outdegree 기반 정렬 방식으로 바뀌게 됩니다.

 

이렇게 되면 기존 indegree 기반 위상 정렬에서 일찍 처리되어야 하는 인덱스들은 오히려 차수가 높아져 뒤늦게 처리되고, 반대로 나중에 처리되어야 했던 인덱스들은 차수가 낮아져 더 빨리 처리됩니다. 이와 같이 반대가 된 처리 순서대로 노드의 개수(N)부터 감소하는 숫자를 부여하면 됩니다.

 

위 그림은 이전에 indegree 기반 정렬의 한계를 설명할 때 가정했던 상황과 동일하게, 나중에 처리된 인덱스가 앞서 처리된 인덱스들보다 더 작은 상황을 나타냅니다. 하지만 이번에는 중요한 차이점이 있습니다. outdegree 기반 정렬 방식을 적용하면서 높은 숫자부터 감소하는 순서로 번호를 부여하기 때문에, 나중에 처리되는 더 작은 인덱스에도 자연스럽게 더 낮은 숫자를 배치할 수 있게 되었습니다. 이로써 모든 간선에 대한 조건을 만족하면서 동시에 사전 순으로 가장 앞서는 결과를 얻을 수 있게 되는 것이죠.

 

이어서 추가로 고려해야 할 부분은 동일한 차수를 가진 여러 인덱스가 존재할 때입니다. 기존에 indegree 기반 정렬에서는 최소 힙을 사용하여 낮은 인덱스에 낮은 숫자를 배치했지만, outdegree 기반 위상 정렬에서는 감소하는 순서로 숫자를 부여하고 있기 때문에 오히려 높은 인덱스에 더 높은 숫자를 배치해야 합니다. 즉, 이 경우에는 최대 힙(max-heap)을 사용해야 합니다.

 

그리고 마지막으로 생각해볼 점은 사이클(Cycle)이 존재하는 경우입니다. 그래프에 사이클이 발생하면 모든 노드를 순서대로 나열할 수 없기 때문에 위상 정렬이 중간에 종료됩니다. 이런 경우 결과적으로 숫자가 부여되지 않은 인덱스가 남아있게 되는데요. 따라서 위상 정렬이 끝난 후 숫자가 부여되지 않은 인덱스가 있는지를 확인하여 그래프에 사이클이 존재하는지, 즉 번호를 수정하는 것이 불가능한 상황인지(출력 결과가 -1인지)를 판단할 수 있습니다.

 

그러면 아까의 그래프에서 간선의 방향을 뒤집은 뒤, 최대 힙을 사용해 위상정렬을 수행하면 [ 5, 3, 2, 4, 1 ]이라는 결과를 얻을 수 있습니다. 이 정렬 결과를 바탕으로 가장 큰 수(5)부터 차례로 숫자를 부여해 수열을 구성하면 [ 1, 3, 4, 2, 5 ]가 되며, 이는 기존의 indegree 기반 정렬 방식으로는 구조적으로 만들 수 없었던, 조건을 만족하면서도 사전순으로 가장 앞서는 결과 수열을 얻을 수 있게 됩니다.

 

결론적으로 이 문제의 핵심은 outdegree 기반 정렬과 최대 힙을 사용해 노드의 수(N)부터 시작하여 감소하는 순서로 숫자를 부여하면서 사전 순으로 가장 앞서는 결과 수열을 구성하는 것이라 할 수 있습니다.

 

 

 

구현하기

먼저 노드의 개수를 입력받고, 인접 행렬 형태로 간선 정보를 입력받습니다. 이때 임의의 간선(A -> B)이 존재한다면, 간선의 방향을 반대로 뒤집어 사용할 것이므로 B가 A를 가리키는 것으로 처리합니다. 즉 A의 차수를 1 증가시키고, B의 인접 리스트에 A를 추가해 줍니다.

 

그 다음 결과 수열을 초기화한 뒤, 위상 정렬을 수행합니다. 이때 처리되는 각 인덱스에 대해 노드의 개수(N)부터 시작하여 1씩 감소하는 값을 차례대로 부여합니다.

 

모든 처리가 끝난 후에도 결과 수열에 아직 숫자가 할당되지 않은(즉, 값이 0인) 인덱스가 남아 있다면, 이는 사이클이 발생하여 그래프를 올바르게 수정할 수 없다는 의미이므로 -1을 출력합니다. 반대로 모든 인덱스에 값이 제대로 부여되었다면, 결과 수열을 순서대로 출력하면 됩니다.

import heapq

# outdegree 기반 위상 정렬 함수
def topological_sort():
    max_heap = []
    for i in range(1, n+1):
        # 차수가 0인 노드를 큐에 추가
        if outdegree[i] == 0:
            heapq.heappush(max_heap, -i)
    
    NUM = n   # 현재 부여할 숫자
    while max_heap:
        now = -heapq.heappop(max_heap)
        result_sequence[now] = NUM
        NUM -= 1
        
        for nxt in graph[now]:
            outdegree[nxt] -= 1
            # 인접 노드의 차수가 0이 된 경우 큐에 추가
            if outdegree[nxt] == 0:
                heapq.heappush(max_heap, -nxt)

n = int(input())
outdegree = [0] * (n+1)
graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
    line = input()
    for j in range(1, n+1):
        # i → j라면 반대로 i의 차수를 올리고, j의 인접 노드에 i를 추가
        if line[j-1] == '1':
            outdegree[i] += 1
            graph[j].append(i)

# 결과 수열 초기화 및 위상 정렬 수행
result_sequence = [0] * (n+1)
topological_sort()

# 결과 수열에 0이 있다면 사이클(그래프를 수정할 수 없는 경우)이므로 -1 출력
if result_sequence[1:].count(0) > 0:
    print(-1)
# 결과 수열 출력
else:
    for i in result_sequence[1:]:
        print(i, end=' ')