위상 정렬 : 그래프 수정(백준 1432번)

▶ 문제 : https://www.acmicpc.net/problem/1432

1432번: 그래프 수정

##### 문제 #####
# N개의 정점이 있는 그래프가 주어지면, 다음과 같은 방법에 의해서 정점의 번호를 다시 매기고 싶다.
# 모든 그래프의 번호는 1보다 크거나 같고 N보다 작거나 같은 번호를 가져야 한다.
# 만약 V1에서 V2로 연결된 간선이 있다면, V2의 번호는 V1보다 커야 한다.
# 위와 같은 조건을 이용해서 그래프의 번호를 다시 매긴 후에, 
# 1번 정점의 새로 고친 번호를 M1, 2번 정점의 새로 고친 번호를 M2, ..., 
# N번 정점의 새로 고친 번호를 MN이라고 하면, N개의 수열이 만들어진다.
# 이 수열을 출력하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에 정점의 개수 N이 주어진다. 
# 둘째 줄부터 N개의 줄에는 인접 행렬 형식으로 입력이 주어진다. 
# 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. 
# N은 50보다 작거나 같은 자연수이다.

##### 출력 #####
# 첫째 줄에 수열의 각 원소를 차례대로 공백을 사이에 두고 출력한다. 
# 만약 그래프의 번호를 수정할 수 없다면 -1을 출력한다. 
# 답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다.

 

▶ 접근 방법

위상 정렬을 이용하여 해결할 수 있었다.
문제에서 주어진 정점들 간의 대소 관계를 그래프로 표현하였다.
동시에 해당 정보를 바탕으로 정점들의 차수를 구하였다.
이때, 어떤 숫자의 차수가 0이라는 것은 해당 숫자보다 큰 숫자가 없다는 것을 의미한다.

차수가 0인 정점을 시작으로 해당 정점과 인접한 정점들의 차수를 줄여나갔다.
그 과정에서 다시 차수가 0이 되는 숫자가 생기는데 그 숫자가 가장 큰 새로운 숫자가 된다.
이런 방식으로 가장 큰 숫자를 하나 씩 찾아나가면서 정렬을 완성하였다.

 

▶ 풀이 코드

import sys, heapq

def topology_sort(N):
    queue = []
    # 정점의 수만큼 아래 과정을 반복한다.
    for num in range(1, N + 1):
        # 만약 차수가 0이면
        if degree[num] == 0:
            # 우선 순위 큐에 넣어준다.
            # 대신 나중에 사전 순으로 출력하기 위해 숫자를 음수 취한다. 
            heapq.heappush(queue,-num)

    while queue:
        now = -heapq.heappop(queue)
        # 처음 힙에서 뽑는 것은 그 어느 숫자보다 큰 것이기에
        # 해당 숫자를 인덱스로 하는 result 리스트에 전체 개수인 N을 할당한다.
        result[now] = N

        # 그 다음으로 큰 숫자를 찾기 위해 아래의 과정을 진행한다.
        for adj_num in graph[now]:
            degree[adj_num] -= 1
            if degree[adj_num] == 0:
                heapq.heappush(queue,-adj_num)
        N -= 1


# 전체 정점의 개수를 입력받는다.
N = int(sys.stdin.readline().rstrip())

# 차수 리스트를 만든다.
degree = [0] * (N + 1)

# 결과를 담을 리스트를 만든다.
result = [0] * (N + 1)

# 정점의 관계를 담을 그래프를 만든다.
graph = [[] for _ in range(N + 1)]
for num in range(1, N + 1):
    info = list(map(int,sys.stdin.readline().strip()))
    # print(info)
    
    # 입력 받은 값을 graph에 넣어 줄때, 
    # 정점의 위치 정보가 1부터 시작한다는 것을 고려하여 idx를 변화시키고 차수도 늘려준다.
    for idx, value in enumerate(info):
        # print(idx, value)
        if value == 1:
            graph[idx+1].append(num)
            degree[num] +=1

print(graph)
print(degree)

topology_sort(N)

if result.count(0) > 1:
    print(-1)
else:
    print(*result[1:])

 

▶ 관련 링크

2021.11.20 - [알고리즘] - 위상 정렬(Topological Sort)이란?

2021.11.22 - [알고리즘] - 위상 정렬 : 줄 세우기(백준 2252번)

2021.11.22 - [분류 전체보기] - 위상 정렬 : 장난감 조립(백준 2637번)