백준 1432_그래프 수정

그래프 수정(백준 1432)

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

처음에는 진입차수를 이용하여,
그래프를 DFS로 탐색하며 값을 교환해주고
‘순환’이 있는 경우, -1을 출력하는 방식을 사용했으나
문제는 ‘답이 여러개 인 경우, 오름차순 출력’ 하는 부분이었다

‘위상정렬’ 의 개념은 알고 있었으나,
구현 방식에 익숙치 않아 고생하였다

[참고 블로그] : https://velog.io/@whddn0221/%EB%B0%B1%EC%A4%80-1432-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%88%98%EC%A0%95-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-mrltwcp5

Code

import sys
import heapq

inp = sys.stdin.readline

n = int(inp().strip())
graph = [[] for _ in range(n)]
outDegree = [0 for _ in range(n)]
answer = [0 for i in range(n)]
child = [[] for _ in range(n)]

# 인접행렬을 입력 받는다
for i in range(n):
    graph[i] = list(*inp().split())
    # 인접리스트로 변환
    for j in range(len(graph[i])):
        if graph[i][j] == '1':
            child[j].append(i)  # 진출 차수로 구하기에 역으로 향하는 녀석에게 넣어준다
            outDegree[i] += 1   # 진출 차수가 있다면 +1을 해준다

def topology_sort(num):
    # heapq 사용 이유
    # 답을 여러 개 구했을때, 가장 오름차순으로 출력하기 위함
    # 최대 힙으로 사용
    heap = []

    for i in range(n):
        if outDegree[i] == 0:
            heapq.heappush(heap,-i) # 최대 힙
    
    while heap:
        # 인덱스 가장 큰 노드를 꺼냄
        # 해당 노드와 연결된 노드들의 진출차수를 빼줌
        curr = -heapq.heappop(heap)
        answer[curr] = num # 큐에서 빼낸 녀석에 가장 큰 숫자(n)을 넣어준다

        for node in child[curr]:
            outDegree[node] -=1 # 진출 차수 빼줌
            if outDegree[node] == 0: # 새로 진출차수 0인 녀석이면 넣어준다
                heapq.heappush(heap,-node)
        
        num -= 1

topology_sort(n)

if answer.count(0) > 2:
    print(-1)
else:
    print(*answer)

해결 아이디어

1. v1 -> v2 의 간선 존재시 v2는 v1보다 커야 한다
   => ‘진입 차수’ 말고 ‘진출 차수’를 이용하여,
   해당 노드의 값이 가장 커야한다는 부분을 인식
   ‘진출 차수’가 0인 정점에 가장 큰수를 넣고
   이와 연결된 다른 정점의 ‘진출차수’를 1 뺴준다
   이후, 0이 된 정점은 큐에 넣어주고 반복함으로
   정답 배열에 큰 수부터 넣어준다
2. 답이 여러 개라면 ‘사전순’ 출력
   => ‘큐’에서 꺼낼 때, 인덱스가 ‘큰 값’을 먼저 꺼내
   정답 배열에 배치한다
   0~n 번 인덱스까지 출력할 때, 더 작은 순으로 출력되도록
   
3. 그래프에서 ‘사이클’을 감지하는 경우, answer가 갱신되지 않으므로
   그에 따라 result의 갱신 여부를 파악한 뒤 -1을 출력