[Coding Test] 코딜리티 연습문제

그래프 순환 체크

1. 문제

경로가 있는 두 배열이 주어질 때, 해당 경로가 순환인지 판단하라

2. 생각

내가 생각한 순환의 조건
1. 목적지에 시작점이 있어야함
2. 목적지에 모든 점이 있어야함
어느 점에서 출발하더라도 모든 점을 방문해야 함.

3. 풀이

def solution(A, B):
    graph = {}
    nodes = []
    for idx in range(len(A)):
        if graph.get(str(A[idx])) is None:
            graph[str(A[idx])] = [B[idx]]
            nodes.append(A[idx])
        else:
            graph[str(A[idx])].append(B[idx])
    print(graph)
    
    for idx in range(len(B)):
        if B[idx] not in nodes:
            nodes.append(B[idx])
    
    node_cnt = len(nodes)
    key_list = list(graph.keys())
    for start_node in nodes:
        cycle = isCycle(start_node, graph, node_cnt)
        if cycle:
            continue
        else:
            return False
    return True

def isCycle(start,graph,cnt):
    queue = []
    visit = []
    queue.append(start)
    while queue:
        node = str(queue.pop(0))
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
        #print(queue)
        #print(visit)
    if len(visit) != cnt:
        return False
    return True