4.7 순서정하기

문제 

프로젝트의 리스트와 프로젝트들 간의 종속관계 ( 즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻 ) 가 주어졌을때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 

 

접근법

위상정렬을 이용해서 해결할 수 있다. 

1. 유입간선 수를 확인하며 순서를 정한다.

def Solution(projects):
    indegree = {}
    adj_list = {}
    for p in projects :
        indegree[p[1]] = indegree.get(p[1],0)+1
        if indegree.get(p[0],-1) == -1 : indegree[p[0]] = 0
        cur_adj_list = adj_list.get(p[0], [])
        cur_adj_list.append(p[1])
        adj_list[p[0]] = cur_adj_list

    q = []
    for node in indegree:
        if indegree[node] == 0:
            q.append(node)
    res = []
    while q :
        cur_node = q.pop(0)
        for next in adj_list[cur_node]:
            indegree[next] = indegree[next] -1
            if indegree[next] == 0 : q.append(next)
        res.append(cur_node)
    return res

2. DFS를 이용하여 해결할 수 있다.

def Solution(projects):
    adj_list ={}
    Isvisit ={}
    res = []
    
    for p in projects :
        cur_adj_list = adj_list.get(p[0],[])
        cur_adj_list = adj_list.append(p[1])
        adj_list[p[0]] = cur_adj_list
    
    if Isvisit.get(p[0], -1) == -1 : Isvisit[p[0]] = 0
    if Isvisit.get(p[1], -1) == -1 : Isvisit[p[1]] = 0

    total_node = len(Isvisit)
    def goDFS(node):
        if Isvisit[node] == 1 : return False
        
        if Isvisit[node] == 0 :
            Isvisit[node] =1
            cand = adj_list[node]
            for c in cand:
                if not goDFS(c): return False
            Isvisit[node] = 2
            res.append(node)
        return True

    for n in Isvisit:
        if Isvisit[n] == 0 :
            if not goDFS(n) :
                return None
    return res