스킬트리

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49993

접근 방법

두 가지 자료구조로 해당 스킬의 선행 스킬이 무엇인지, 그리고 배운 스킬을 관리했다.

• graph[스킬] = 선행스킬
• visited[스킬]

우선, graph에 해당 노드가 없으면 들어오는 노드가 없다는 뜻이다. 즉, 시작노드이므로 그냥 visited 체크 가능하다.

만약 graph[스킬]이 존재하면(=선행 스킬이 있는 경우), visited가 안되어 있는 경우 조건을 만족하는 스킬트리가 아니므로 정답으로 세지 않는다.

코드

def solution(skill, skill_trees):
    graph = dict()
    for i in range(1, len(skill)):
        first, sec = skill[i-1], skill[i]
        graph[sec] = first
    cnt = 0
    for skills in skill_trees:
        visited = {node : False for node in skill}
        for x in skills:
            if x not in graph:
                visited[x] = True
            else:
                todo = graph[x] #선행노드
                if not visited[todo]: #선행노드를 방문하지 않았으면 성립 X
                    break
                else:
                    visited[x] = True
        else: 
            cnt += 1
    return cnt