[SWEA][Python]#1267. 작업순서

📌풀이

내가 쓴 풀이(성공)

from collections import deque, defaultdict

        
for i in range(1,11):
    #인풋값 받아옴
    vertex, edge = map(int,input().split())
    edge_list = list(map(int,input().split()))
    
    #각 노드의 연결 노드, 연결된 노드 파악용 딕셔너리
    connect = defaultdict(list)
    parent = defaultdict(list)
    #해당 노드를 완료했는가 판단
    done = [False for _ in range(vertex)]
    #경로를 넣어놓을 리스트
    path = []
    
    #받아온 엣지들을 기준으로 connect, parent 설정
    for idx in range(edge):
        start = edge_list[idx*2]
        end = edge_list[idx*2 + 1]
        connect[start].append(end)
        parent[end].append(start)
        
	
    d = deque()
    #부모가 없는 노드들을 넣어놓음(root)
    for node_num in range(1, vertex+1):
        if node_num not in parent :
            d.append(node_num)
    
    flag = 0
    while d :
        #왼쪽 값을 빼서 판단
        current = d.popleft()   
    	
        #루트노드인 경우, 완료로 표시
        if current not in parent:
            done[current - 1] = True
        #아닌 경우, 부모 노드들이 완료됐는지 판단
        else : 
            for parent_num in parent[current]:
                #완료하지 않은 경우
                if not done[parent_num - 1]:
                    flag = 1
                    break
            #부모노드가 완료되지 않은 경우, 다시 d에 집어넣음
            if flag :
                d.append(current)
                flag = 0
                continue
            else :
                done[current -1] = True
    	
        #현재 노드를 경로에 추가, 자식 노드들을 d에 집어넣음
        path.append(current)
        for next_node in connect[current]:
            if not done[next_node - 1] and next_node not in d :
                d.append(next_node)
	#경로가 들어있는 리스트를 문자열로 변환
    result = ' '.join(list(map(str,path)))        
    print(f'#{i} {result}')
    

📌후기

처음에 그래프와 노드 클래스를 만들어서 문제를 해결하려고 했는데, 메모리 오버플로우가 나면서 해결되지 못했었다. 그래서 연결 부분, 부모 노드 부분만 따로 딕셔너리로 만들어서 해결할 수 있었다. BFS를 생각하면서 풀긴 했는데, BFS가 맞는걸까...?