#36 위상 정렬(Topological Sorting)

 지난 글에서 위상 정렬을 구현하는 방법으로 진입 차수 테이블과 큐를 사용한 방법을 알아보았다.  이번에는

위상 정렬을 구현하는 다른 방법인 dfs(깊이우선탐색)를 활용한 방법을 알아보고 몇 개의 문제를 해결해본다.

 

1. 줄 세우기(https://www.acmicpc.net/problem/2252) - 구현

 진입 차수 테이블과 큐를 사용한 방법의 경우, 진입 차수가 0인 노드를 모드 큐에 넣으며 탐색해나가는

bfs(너비우선탐색)의 형태로 구현된다. 그리고 그 방식에서는 큐에서 뽑혀 탐색된 노드 순서가 곧 정렬 순서가 되었다. dfs를 활용한 방식에서는 정확히 그 반대라고 생각하면 편하다. 즉, 탐색이 가장 먼저 종료된 순서의 역순이 곧

정렬 순서가 된다.  이 방식으로 줄 세우기 문제를 해결한 코드는 다음과 같다.

 

import sys
sys.setrecursionlimit(100000)

input = sys.stdin.readline


def sol2252():
    # 학생 수 n, 키 비교 결과 수 m
    n, m = map(int, input().split())
    
    # 그래프, 진입 차수 테이블 생성
    # bfs 형태의 구현과 달리 진입 차수 테이블은 생성이후 수정할 일이 없음
    g = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for _ in range(m):
        a, b = map(int, input().split())
        g[a].append(b)
        degree[b] += 1
    
    # dfs를 활용한 위상 정렬 구현
    def dfs(d):
        nonlocal answer
        # 현재 노드 방문처리
        visit[d] = True
        
        # 아직 방문하지 않은 자식노드 방문
        for child in g[d]:
            if not visit[child]:
                dfs(child)
               
        # 탐색이 종료된 노드를 answer에 삽입
        answer.append(d)
        
    # 방문여부 리스트
    visit = [False] * (n + 1)
    
    # 정렬 결과 리스트
    answer = []
    
    # 처음부터 진입 차수가 0인 노드로부터 탐색 시작 
    for i in range(1, n + 1):
        if not degree[i]:
            dfs(i)
            
    # 정렬 결과 리스트를 뒤집어 출력 형식에 맞춰 반환
    return ' '.join(map(str, answer[::-1]))

 

 

2. ACM Craft (https://www.acmicpc.net/problem/1005)

 건설 규칙과 건물을 완성하는데 걸리는 시간이 주어졌을 때, 특정 건물을 건설하는데 걸리는 최소시간을 구하는 문제.

건물을 노드, 건설 규칙을 간선으로 생각하면 위상 정렬로 쉽게 해결할 수 있는 문제이다.  다만 각 노드(건물)까지

소요되는 최소 시간을 매번 다시 계산할 순 없기 때문에 간단한 동적계획법을 적용할 필요가 있다. 이를 해결한 코드는

다음과 같다.

 

import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def sol1005():
    # dfs(d) = dp[d] 는 d 번 건물을 건설하기 위해 필요한 최소 비용
    def dfs(d):
        # 아직 건물 d를 건설하기 위한 최소비용이 계산되지 않았다면 계산에 들어간다.
        # 건물 d를 건설하기 위한 최소비용은 반드시 먼저 건설되어야할 건물의 최소 비용 중 
        # 가장 큰 비용에 건물 d를 건설하기 위해 필요한 비용을 합친 값이 된다.
        if dp[d] == -1:
            dp[d] = max([dfs(p) for p in g[d]], default=0) + cost[d]
            
        # 건물 d를 건설하기 위한 최소 비용을 반환
        return dp[d]

    # 케이스별 정답 리스트
    answer = []
    for t in range(int(input())):
        # 건물 수 n, 건설 규칙 수 k
        n, k = map(int, input().split())
        
        # 각 건물을 완성하는데 필요한 시간
        cost = [0, *map(int, input().split())]

        # 그래프를 생성
        g = [[] for _ in range(n + 1)]
        for _ in range(k):
            x, y = map(int, input().split())
            
            # 이 문제의 경우 정확하게 건물 w를 짓는데 드는 최소 비용만을 구하는 문제
            # 노드 전체를 위상정렬하는 문제와 다르게 건물 w를 짓기 위해 지어야 하는 
            # 건물들의 최소 비용만을 탐색하는 것이 효율적이기 때문에
            # 역탐색을 위해 그래프의 인접리스트에 갈 수 있는 노드가 아닌 
            # 현재 노드로 올 수 있는 노드를 저장한다.
            g[y].append(x)

        # dfs(w)를 구하여 정답 리스트에 저장
        dp = [-1] * (n + 1)
        w = int(input())
        answer.append(dfs(w))

	# 출력 형식에 맞춰 정답 리스트 반환
    return '\n'.join(map(str, answer))