방향 비순환 그래프(DAG)위에서 다이나믹 프로그래밍 배우기

1. 방향 비순환 그래프(Directed acyclic graph)

 

사이클이 존재하지 않는 방향 그래프

 

정점 u에서 출발했을때, u로 돌아오는 방법이 없다.

 

다음과 같은 그래프는 방향 비순환 그래프(DAG)이다.

 

 

 

2. 한 정점에서 다른 정점까지 가장 긴 경로의 길이

 

정점 v에 대하여 DP[v]를 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이라고 정의한다면...

 

다음과 같이 v에서 c1,c2,c3,...로 갈 수 있을텐데, c1,c2,c3,...에서 출발하여 도달할 수 있는 가장 긴 경로의 길이

 

DP[c1],DP[c2],...가 이미 구해져있다면...

 

DP[v] = max(wi + DP[ci])으로 구할 수 있을 것이다.

 

 

 

 

다이나믹 프로그래밍은 이미 해결한 작은 문제를 이용해서 더 큰 문제를 해결하는 방법이다.

 

즉 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이를 구할려고하는 시점에,

 

더 작은 문제인 c1,c2,c3,...에서 출발할때 도달할 수 있는 가장 긴 경로의 길이는 이미 구해져있어야한다.

 

이렇게 작은 문제에서 큰 문제로 해결하는 순서가 있다면 그래프에서 다이나믹 프로그래밍을 적용할 수 있다.

 

 

3. 방향 비순환 그래프의 순서

 

방향 비순환 그래프를 잘 보면, 왼쪽 노드에서 오른쪽 노드로 순서대로 이동할 수 있을 것 같다는 느낌이 든다

 

 

 

방향 그래프의 노드들을 방향성에 거스르지 않도록 순서대로 정렬하는 위상정렬 알고리즘을 이용한다면,

 

모든 노드들을 방향성의 순서대로 정렬할 수 있다.

 

https://deepdata.tistory.com/498

그래프의 노드를 정렬하는 위상정렬 정복하기

 

 

간단히 설명하자면 주어진 그래프에서 들어오는 간선이 없는 정점들을 하나씩 제거해나가면,

 

제거해나간 정점 순서대로 위상정렬이 된다

 

먼저 다음과 같이 1번 정점은 들어오는 간선이 없으니 제거하고,

 

 

 

다음 2번과 3번 정점이 들어오는 간선이 없으므로 이들을 제거한다.

 

제거하는 순서는 2번과 3번이 바뀔 수 있는데 상황에 따라 다르다.

 

 

 

 

2번 3번을 제거하면 다음과 같이 4번,5번이 들어오는 간선이 없다.

 

 

다음 들어오는 간선이 없는 6번을 제거하면, 7번 8번 정점이 들어오는 간선이 없는 정점이 된다.

방향 비순환 그래프가 주어질때, 주어진 노드를 위상정렬하여 각 노드의 순서를 파악할 수 있다.

 

 

 

그러면 각 노드의 위상정렬 순서대로 순회해서 DP[v]를 구하여 최종적으로 원하는 정점에 대하여 가장 긴 경로의 길이를 구할 수 있게 된다.

 

물론 이 문제의 경우는... '정점 v에서 출발할 때 가장 긴 경로의 길이 DP[v]'로 문제를 정의하고 있는데,

 

DP[v]를 구하기 위해서는 v 다음 정점 c1,c2,c3,...의 DP[c1],DP[c2],...를 알고 있어야한다.

 

그래서 위상정렬의 역순으로 순회해야겠다.

 

이런건 응용의 영역이라서...

 

 

 

 

핵심은 방향 비순환 그래프가 주어질때 위상정렬을 이용해 노드의 순서를 파악하고...

 

해당 노드 순서대로 순회해서 다이나믹 프로그래밍을 수행하여 문제를 해결할 수 있다는 점

 

 

4. 연습문제1

 

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

 

 

5. 풀이

 

방향 그래프가 주어질때, w까지 도달하는데 걸리는 최소 시간을 구하는 문제

 

DAG위에서의 다이나믹 프로그래밍으로 해결할 수 있다.

 

u에서 v1,v2,v3,...로 이동할 수 있다면, 모든 v1,v2,v3,..의 건물을 건설해야 다음 건물을 건설할 수 있으므로

 

최대 시간을 선택해서 저장해야한다.

 

먼저 그래프가 주어질때, 노드들의 순서를 위상정렬로 구하면 된다

 

위상정렬을 위해서는 각 노드의 들어오는 간선의 개수를 구해야한다.

 

이는 그래프를 입력받을때, u에서 v로 가는 간선이 존재한다면 v의 들어오는 간선의 개수를 1 증가시키면 된다

 

T = int(stdin.readline())

for _ in range(T):
    
    n,k = map(int,stdin.readline().split())

    D = list(map(int,stdin.readline().split()))

    graph = [[] for _ in range(n+1)]
    indegree = [0]*(n+1) #각 노드의 들어오는 간선의 개수

    for _ in range(k):
        
        u,v = map(int,stdin.readline().split())

        graph[u].append(v) 
        
        #u에서 v로 이동하는 간선이 존재한다면, v의 들어오는 간선의 개수 1 증가
        indegree[v] += 1

 

 

1) 위상정렬은 최초에 들어오는 간선의 개수가 0개인 노드를 큐에 모두 넣고 시작한다.

 

2) 큐에서 노드를 뽑아, 위상정렬 순서 배열에 넣어준다.

 

3) 뽑은 노드를 제거하면서 해당 노드와 연결된 노드의 들어오는 간선의 개수를 1씩 감소시킨다.

 

4) 들어오는 간선의 개수가 1개씩 감소한 노드들 중, 들어오는 간선의 개수가 0개가 된 노드가 있다면, 큐에 넣어준다.

 

5) 큐가 빌때까지 반복할때, 위상정렬 순서 배열에 들어간 노드들이 순서대로 위상정렬된 결과이다.

 

#위상정렬
def topology_sort(graph,indegree,n):
    
    queue = deque([])
    
    #들어오는 간선의 개수가 0개인 노드들을 모두 큐에 넣는다.
    for i in range(1,n+1):
        
        if indegree[i] == 0:
            
            queue.append(i)
    
    order = []

    while queue:
        
        u = queue.popleft() #노드 하나를 빼고,

        order.append(u) #정렬 결과 배열에 넣어준 다음,

        for v in graph[u]: #u와 연결된 노드 v에 대하여...
            
            indegree[v] -= 1 #u를 제거했으므로 v의 들어오는 간선의 개수는 1씩 감소

            if indegree[v] == 0: #이때, v의 들어오는 간선의 개수가 0개가 된다면...
                
                queue.append(v) #큐에 넣어준다
    
    return order

 

 

DP[u]가 정점 u 위의 건물을 건설하는데 걸리는 최소 시간이라고 정의한다면...

 

u에서 v로 이동할 수 있을때, v로 들어올 수 있는 모든 u에 대하여... dp[v] = max(dp[v], dp[u]+d[v-1])이 된다.

 

위상정렬된 배열을 알고 있다면, 순서대로 순회해서 dp배열을 채워 넣는다.

 

최초 dp배열을 0으로 초기화했는데, 각 정점마다 건설하는데 걸리는 시간이 있으므로...

 

dp[u] = max(dp[u], d[u-1])로 초기화하고 시작

 

dp배열을 모두 채워넣으면 w까지 건설하는데 걸리는 최소 시간을 원하므로 dp[w]가 답이다.

 

def solve(D,graph,order,w,n):
    
    dp = [0]*(n+1)

    for u in order: #위상정렬 순서대로 순회해서...
        
        if dp[u] < D[u-1]:
            
            dp[u] = D[u-1] #각 정점 u의 건설시간의 시작 시간을 dp[u] = max(dp[u],d[u-1])로 초기화
        
        for v in graph[u]: #v로 들어올 수 있는 모든 u에 대하여...
            
            #이전에 건설된 시간 dp[u]에 해당 정점 v의 건설시간 d[v-1]을 더한게 dp[v]
            #가능한 dp[v]중 최댓값으로 저장
            if dp[u]+D[v-1] > dp[v]:
                
                dp[v] = dp[u]+D[v-1]
    
    return dp[w] #w까지 건설하는데 걸리는 최소시간이 답

 

 

6. 연습문제2

 

E - Non-Decreasing Colorful Path (atcoder.jp)

E - Non-Decreasing Colorful Path

 

 

7. 풀이

 

무향 연결 그래프(connected undirected graph)가 주어질때 각 노드에 숫자가 적혀있는데 1번부터 N번까지 이동하면서 적힌 숫자를 순서대로 나열한다.

 

이 수열이 비감소수열을 이루게할때, 서로 다른 숫자의 개수가 최대가 되도록 할려면?

 

무향그래프(undirected)는 양방향으로 이동할 수 있다는 뜻이고

 

연결 그래프(connected graph)라면, 모든 정점간 경로가 존재하는 그래프이다.

 

따라서 1번부터 N번까지 경로는 반드시 존재한다.

 

예를 들어 다음과 같은 그래프가 있다..

 

 

 

근데 먼저.. 비감소수열을 이루도록 이동해야하므로.. 애초에 위 그래프에서 숫자가 증가하는 방향대로 이동할 수 있게 한다면..

 

방향 비순환 그래프(DAG)가 되므로, 다이나믹 프로그래밍으로 해결할 수 있다.

 

 

 

 

근데 문제는 원래 그래프는 방향 비순환 그래프가 아닌데...

 

같은 숫자가 적힌 노드들 간에는 이동해도 점수가 증가하지 않으므로.. 같은 숫자가 적힌 노드들을 하나로 합쳐버린다

 

원래 이렇게 생긴 그래프를...

 

 

 

 

다음과 같이 만들어버린다면?

 

 

이렇게 만드는건 union find로 가능하다.

 

그래프를 입력받을때, u,v에 대하여 u와 v에 적힌 숫자가 서로 같다면.. union하면 된다

 

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x],parent)
    
    return parent[x]

def union(a,b,parent):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[a] = b
    
    else:
        
        parent[b] = a

n,m = map(int,stdin.readline().split())

A = [0] + list(map(int,stdin.readline().split()))

graph = [[] for _ in range(n+1)]

parent = [i for i in range(n+1)]

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    graph[u].append(v)
    graph[v].append(u)

    if A[u] == A[v]:
        
        union(u,v,parent)

 

 

그러면 양방향 그래프지만, 애초에 숫자가 증가하는 순서대로 이동해야 의미있으므로...

 

방향 비순환 그래프로 생각할 수 있다.

 

 

 

노드들의 순서는 어떻게 구할 수 있을까?

 

위상정렬 알고리즘으로 정렬 해야하나??

 

결국에 이동하는 방향은 숫자가 증가하는 방향대로여야한다는 점에 주목한다.

 

굳이 그럴 필요 없이 노드에 적힌 숫자를 알고 있으므로 (노드 번호, 숫자)를 정렬하기만 하면..

 

그것이 위상정렬이 된다.

 

이제 노드 v에 대하여 v까지 도달하는데 걸리는 가장 긴 경로를 구하는 문제로 바뀌었다.

 

정렬된 노드를 순서대로 순회하여, u에서 v로 이동할 수 있을때 dp[v] = max(dp[v], dp[u]+1)이 된다.

 

INF = 10**18

dp = [-INF]*(n+1)

B = []

for i in range(1,n+1):
    
    B.append((i,A[i]))

B.sort(key = lambda item: item[1])

dp[find_parent(1,parent)] = 1

for u,_ in B: #위상정렬
    
    u1 = find_parent(u,parent)

    for v in graph[u]:    

        if A[v] > A[u]:
            
            v = find_parent(v,parent)
            dp[v] = max(dp[v],dp[u1]+1)

print(max(0,dp[find_parent(n,parent)]))

 

 

근데 이 문제는 이제 조금 더 생각해야하는게 

 

먼저 1번부터 N번까지 이동하는데 걸리는 가장 긴 경로를 찾는 문제이므로 결국 DP[N]이 답이다.

 

1번부터 시작하기 때문에 DP[1] = 1이 될 것이고

 

애초에 DP 초기값을 0이 아니고 음의 무한대로 해야하는데 왜 그래야할까?

 

'1번부터 N번까지 이동하는데, 걸리는 가장 긴 경로'를 구하는 문제인데

 

일단 위상정렬된 노드 순서가 1번부터가 아닐 수 있다는게 문제다.

 

예를 들어 노드 번호가 다음과 같다면?

 

 

 

 

 

근데 위상정렬된 노드 번호는 2,3,4,1,5이다.

 

근데 만약 초기값을 0으로 해두고 DP[1] = 1로 한다면?

 

DP[2] = 0, DP[3] = 1, DP[4] = 1, DP[1] = 1이고..

 

3번에서 1번으로 갈때, DP[1] = max(dp[1], DP[3] + 1)이 되어, dp[1] = 2가 된다.

 

그러다보니 1번에서 5번으로 최대 길이는 분명히 2인데, 3이 나오는 잘못된 답을 낸다.

 

 

 

 

그래서 처음 초기값을 음의 무한대로 해서, 위상정렬된 순서대로 1번 노드 이전의 노드들은 dp배열 채울때 dp[1] = 1보다 작게 되어있어야한다.

 

즉 1번 이전의 노드들은 어떻게 오든 상관 없기 때문에 지워버린다는 소리다.

 

그래야 올바르게 1번에서 5번으로 가는 최장 거리가 2로 잘 나온다

 

 

 

다음으로 각 노드들을 union find로 해서 숫자가 같은 노드들은 하나로 합쳐서 생각하고 있으므로...

 

dp배열에 채울때 사용하는 노드 번호는 각 노드 번호의 parent 번호를 사용해야한다.

 

참고로 parent[v]랑 find_parent(v,parent)는 다르다.

 

parent[v]는 v의 한 단계? 위 부모지만 find_parent(v,parent)는 v의 최종적인 대표자(v의 parent의 parent의 parent의... parent)를 구해준다

 

dp[find_parent(1,parent)] = 1

for u,_ in B: #위상정렬
    
    u1 = find_parent(u,parent)

    for v in graph[u]:    

        if A[v] > A[u]:
            
            v = find_parent(v,parent)
            dp[v] = max(dp[v],dp[u1]+1)

print(max(0,dp[find_parent(n,parent)]))

 

 

다음과 같이 u = find_parent(u,parent)로 해버린다면?

 

for u,_ in B: #위상정렬
    
    u = find_parent(u,parent)

    for v in graph[u]:    

        if A[v] > A[u]:
            
            v = find_parent(v,parent)
            dp[v] = max(dp[v],dp[u]+1)

 

 

for v in graph[u]에서 오류가 생길 가능성이 있다.

 

원래 u와 u의 parent가 연결된 간선은 서로 다른 정점일 수 있으니까

 

아래 그래프만 봐도 답이 나온다

 

원래 u는 50과 연결되어 있는데 parent(u)는 50과 연결되어 있지 않다.

 

 

 

 

참고로 다음과 같이 해도 AC를 받긴 하나보다...

 

이미 for v in graph[u]:에서 graph[u]가 정해져서 그런지

 

그 안에서 u = find_parent(u,parent)해버려도 graph[u]가 안바뀌나봐?

 

dp[find_parent(1,parent)] = 1

for u,_ in B: #위상정렬

    for v in graph[u]:
        
        u = find_parent(u,parent)
        v = find_parent(v,parent)
        
        if A[v] > A[u]:
            
            dp[v] = max(dp[v],dp[u]+1)

print(max(0,dp[find_parent(n,parent)]))

 

 

진짜 그러네... 이건 좀 신기하네