[BOJ] 9466 - 텀 프로젝트 (Python)

 

 

아이디어 #1

 

DFS로 탐색해 나가다 현재 탐색에서 사이클이 발견되는 경우 해당 사이클에 포함되는 노드들 수를 결과값에서 뺀다.

 

 

풀이 #1

 

결과값을 노드 개수로 초기화하고, 차례로 방문하지 않은 노드들로부터 DFS를 시작한다.

지나온 노드들을 path 리스트에 저장하고 그 인덱스를 idx_dict 딕셔너리에 저장한다.

다음에 방문할 노드가 이미 path 리스트에 존재하는 경우 해당 노드를 포함하여 이후 노드들의 개수를 결과값에서 뺀다.

path 리스트에 존재하지는 않지만 이미 방문한 노드인 경우 현재 탐색을 종료한다.

 

import sys

input = sys.stdin.readline

T = int(input())
for t in range(T):
    N = int(input())
    graph = [0]+list(map(int, input().split()))
    visited = [0]*(N+1)
    res = N
    for i in range(1, N+1):
        if visited[i]:
            continue
        idx = i
        idx_dict = dict()
        path = []
        while True:
            visited[idx] = 1
            path.append(idx)
            idx_dict[idx] = len(path)
            _idx = idx_dict.get(graph[idx], 0)
            if _idx:
                res -= len(path[_idx-1:])
                break
            if visited[graph[idx]]:
                break
            idx = graph[idx]
    print(res)

 

 

 

아이디어 #2

 

다른 분들의 코드를 참고한 결과, 말단 노드에서 사이클이 발견되기 전까지의 노드 개수를 세면 결과값임을 알 수 있었다.

 

 

풀이 #2

 

번호가 선택된 만큼 child 리스트에서 해당 번호의 노드 자식 수를 증가시킨다.

자식이 없는 말단 노드의 경우 leaves 리스트에 추가한 후 리스트를 돌면서 부모 노드의 자식 수를 감소시킨다.

감소시킨 부모 노드의 자식 수가 0이면(사이클이 존재하지 않으면) leaves 리스트에 추가한다.

 

import sys

input = sys.stdin.readline

T = int(input())
for t in range(T):
    N = int(input())
    graph = [0]+list(map(int, input().split()))
    child = [0]*(N+1)
    for i in graph:
        child[i] += 1
    leaves = [i for i in range(1, N+1) if child[i] == 0]
    for leaf in leaves:
        idx = graph[leaf]
        child[idx] -= 1
        if child[idx] == 0:
            leaves.append(idx)
    print(len(leaves))