백준 텀 프로젝트 9466 파이썬

​

​

7달 전에 한 10트 도전해서 안되서 포기하고, 오늘 다시 풀어봤다. 오늘도 의기양양하게 풀었으나 82%에서 TLE 발생해서 뭐지뭐지 한참을 고민했다. 결론은 어거지로 푼 거 같으니 며칠 내로 기억이 희미해질 쯤에 다시 풀어봐야겠다.

​

​

82% 시간 초과 해결을 위해서 거의 4시간을 붙잡고 있었던 거 같다. 82%에서 시간초과가 발생하는 이유는 간단한다. 탐색하는 모수가 너무 과하기 때문이다. 즉, 탐색 모수를 최소화 해야한다.

​

사이클이 형성되는 경우는 다음과 같이 2가지가 있다.

1. 1 → 2 → 3 → 4 → 1

2. 1 → 2 → 3 → 4 → 5 → 3

​

​

1번은 대부분의 사람들이 잘 처리하지만, 나 같이 TLE가 발생한 사람들은 2번에서 처리하는 방법에서 많이 헤맸던 거 같다.

​

2번을 통해서 사이클을 확인하게 되더라도 3,4,5뿐만 아니라 1,2을 모두 탐색하지 않아도 된다. 왜냐하면 3,4,5가 싸이클이 만들어지면서 1,2는 싸이클이 만들어지지 않는 것이 확정되었기 때문이다. 따라서 DFS로 탐색을 할 때, 싸이클은 싸이클이라고 표시해주고, 싸이클이 안 만들어진 곳은 앞으로 방문하지 않아도 된다는 것을 잘 기록해줘야한다.

​

이렇게 하면 모든 노드는 최대 각 2n번만 탐험하면 된다. 따라서 문제의 해결이 가능해지는 것이다.

 

import sys

def init(my_list):
    for i in list(map(int,sys.stdin.readline().split())):
        my_list.append(i)
    return my_list

def solsol(start_point):
    global ans

    #DFS 용
    stack = [start_point]

    #경로 체크용
    d_stack = [start_point]

    while stack :
        now_point = stack.pop()
        next_point = my_list[now_point]

        # 한번도 방문한 적이 없는 경우, 계속 방문한다.
        if v[next_point] == 0  :
            v[next_point] = now_point
            stack.append(next_point)
            d_stack.append(next_point)

        # 한번이라도 방문한 적이 있는 경우
        else :
            # 이미 경로가 없다고 판별된 곳
            if v[next_point] == -1 :
                break

            # 사이클이 형성된 곳
            if v[next_point] != 9876543210:


                while d_stack:
                    point = d_stack.pop()
                    if v[point] != 9876543210 :
                        ans +=1
                        v[point] = 9876543210
                    if point == next_point:
                        break
    while d_stack :
        point = d_stack.pop()
        v[point] = -1





for _ in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
    my_list = [0]
    v = [0 for _ in range(n+1)]

    my_list = init(my_list)
    ans = 0

    for student in range(1, n+1):
        if my_list[student] == student :
            v[student] = 9876543210
            ans +=1

    for student in range(1, n+1):
        if v[student] == 0 :
            solsol(student)
    print(n - ans)