[BOJ] Q9466 텀 프로젝트

[BOJ] Q9466 텀 프로젝트

Question

Language: Python

Difficulty: Gold 4

해당 문제는 1->2->3->1과 같이 출발점에서 시작한 노드가 다시 출발점으로 돌아오는 사이클을 찾아서, 사이클에 포함되어 있지 않는 학생들의 수를 찾아내는 것이다.

자기 자신으로의 사이클도 존재할 수 있다는 점에서, dfs를 통한 cycle 탐색을 수행하면 된다. 이때, 아래와 같이 cycle이 발생하게 되면, 5번 노드의 경우는 문제의 조건에 의해 사이클에 포함되지 않으므로 제거시켜줘야한다.

if visited[adj_vertex]:
    if adj_vertex in path:
        visited[vertex]=True
        count+=len(path[path.index(adj_vertex):])
    break
else:
    stack.append((adj_vertex))

Solution

def solution():
    visited=[False] *(num+1)
    count=0
    for start_vertex in range(1,num+1):
        if visited[start_vertex]:
            continue        
        stack=[(start_vertex)]
        path=[]
        while stack:
            vertex=stack.pop(0)
            visited[vertex]=True
            path.append(vertex)
            adj_vertex=edges[vertex]
            if visited[adj_vertex]:
                if adj_vertex in path:
                    visited[vertex]=True
                    count+=len(path[path.index(adj_vertex):])
                break
            else:
                stack.append((adj_vertex))

    return num-count

if __name__ == "__main__":
    test_cases=int(input())
    for _ in range(test_cases):
        num=int(input())
        edges=[0]+list(map(int,input().split())) 
        print(solution())