[BOJ] 9466 텀 프로젝트 - 파이썬

TIP

문제 링크 (opens new window)

문제 요약

사이클에 속해있지 않은 노드(학생)의 개수를 구해라.

첫번째 접근

dfs 탐색 시잠점과 탐색 종료점이 같다면 사이클이라는 정보를 이용할수있겠다 생각했습니다. dfs 를 돌면서 이미 경로에 있는 노드를 방문하려 한다면, 종료합니다.

예를들어 (1 -> 2 -> 3 -> 1)인 그래프가 있다고 할때 dfs(1)을 실행시키면 재귀적으로 dfs(3) 까지 실행되고있는 시점에 [1, 2, 3]이 경로에 저장되있을거고, 이때 다음 노드인 1이 이미 경로에 있기때문에 경로에 1을 추가하고 종료시킵니다. 그럼 dfs(1)을 호출한 측에서는 [1,2,3,1]이라는 경로를 받게됩니다. 시작점과 끝점이 같기때문에 사이클임을 확인할수있습니다.

이런식이면 사이클임을 알수있으니 모든 노드에 대하여 이 방법을 반복하면 중복해서 요소에 접근하게되고, 시간초과가 발생합니다.

즉 위의 방법은 최적화가 필요했습니다. 단순히 시작점과 종료점만을 체크하는 방식으로는, 경로안에 사이클이 있는 경우를 찾지는 못했습니다. 만약 [1,2,3,4,2] 가 경로라면 시작점과 도착점이 1과 2로 다르기때문에 사이클이 아니라고 판단하게됩니다.

개선한 방법(AC)

경로가 [1,2,3,4,2] 와 같이 나왔을때 경로의 마지막 요소와 같은 요소를 찾으면 됩니다. 그러면 사이클을 찾을수있으며, 각 요소를 한번씩만 방문해도 문제를 풀수있습니다.

import sys

sys.setrecursionlimit(1000030)
input = sys.stdin.readline


def main():
    tc = int(input())
    for _ in range(tc):
        input()
        students = [int(_) - 1 for _ in input().split()]

        print(solve(students))


def solve(students):
    n_student = len(students)
    visited = [False for _ in range(n_student)]
    cnt = 0

    for node in range(n_student):
        if not visited[node]:
            path = [node]
            dfs(students, visited, path, node)
            # ex,  path [4, 7, 6, 4]
            # ex2, path [1, 3, 3]
            start = next((i for i, x in enumerate(path)
                          if x == path[-1]
                          and i != len(path) - 1), None)

            if start is not None:
                cnt += len(path) - start - 1

    return n_student - cnt


def dfs(students, visited, path, node):
    visited[node] = True
    next_node = students[node]
    path.append(next_node)

    if not visited[next_node]:
        dfs(students, visited, path, next_node)


main()

위상정렬 접근(AC)

indegree 가 0 이라면 사이클에 속할수가 없습니다. 그렇기에 indegree 가 0 인 노드들을 찾아서, cnt(사이클에 속하지 않은 노드 개수)를 늘리고, 노드를 그래프에서 제거합니다. 노드를 그래프에서 제거한다는 것은 해당 노드가 가리키는 노드의 indegree 를 감소 시키는 것입니다.

이후 indegree가 0인 노드가 또 생기게되고 위의 과정을 반복해나가면 답을 구할수있습니다.

import sys

sys.setrecursionlimit(1000030)
input = sys.stdin.readline


def main():
    tc = int(input())
    for _ in range(tc):
        input()
        students = [int(_) - 1 for _ in input().split()]
        indegree = [0 for _ in range(len(students))]
        visited = [False for _ in range(len(students))]

        for st in students:
            indegree[st] += 1
        cnt = 0
        for i in range(len(students)):
            cur = i
            while indegree[cur] == 0 and visited[cur] == 0:
                visited[cur] = True
                indegree[students[cur]] -= 1
                cur = students[cur]
                cnt += 1
        print(cnt)

main()