[백준 9466] 텀 프로젝트

🍎 [백준 9466] 텀 프로젝트

문제 링크

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

⚾ 코드

import sys
sys.setrecursionlimit(1000001)  # 재귀 깊이 설정
input = sys.stdin.readline


def find_group(start):
    global group
    visited[start] = True

    cycle.append(start)  # cycle 리스트에 삽입

    if visited[student[start]] == True:  # 만약 다음 노드가 방문을 했다면
        if student[start] in cycle:  # 다음 노드가 사이클 안에 있다면
            # 다음 노드부터 그 이후의 값을 group 리스트에 삽입
            group += cycle[cycle.index(student[start]):]
        return
    else:
        find_group(student[start])  # 다음 노드를 방문하지 않았다면 이어서 반복


T = int(input())
for _ in range(T):
    n = int(input())
    student = [0] + list(map(int, input().split()))
    visited = [True] + [False]*n
    group = []

    for i in range(1, n+1):
        if visited[i] == False:
            cycle = []
            find_group(i)

    print(n-len(group))

 

🔔 해결 과정 & 깨달은 점

- 간단해 보였지만 생각보다 푸는 데 까지 시간이 꽤 걸렸다.

- 처음에는 시간 초과, 그 다음에는 메모리 초과, 그리고 런타임 에러를 거쳐 드디어 맞췄다..!

- 노드에 노드를 이어서 가는 것이기 때문에 dfs 알고리즘을 사용해서 풀었다.

- 아래의 이미지를 보면서 코드를 설명해보려고 한다.

- 위의 예시는 백준에서 예제로 준 것을 살짝 변경한 것이다.

- 예를 들어 1번 부터 시작했을 때 1 -> 4 -> 7 -> 6 이 순으로 탐색하게 된다. 6번은 4번을 향하고 있지만, 4번은 이미 방문한 노드이므로 조건문 안으로 들어간다. 

- 6번이 향하고 있는 4번은 cycle 안에 있기 때문에 4번부터 슬라이스를 해 group 안에 넣는다.

- 만약 cycle 안에 없다면 어떻게 될까? 그게 바로 그 다음 줄에 있는 예시이다.

- 1번의 탐색을 마친 후 2번의 차례가 된다.

- 2 -> 1의 순으로 탐색을 하고, 1번은 4를 향하고 있지만, 4번은 이미 방문한 노드이므로 조건문 안으로 들어간다.

- 그러나 1번이 향하고 있는 4번은 cycle 안에 없기 때문에 gruop 안에 추가되지 않는다.

 

- RecursionError는 재귀와 관련된 에러이다. sys.setrecursionlimit(1000001) 와같이 적어서 재귀 깊이를 설정해주어야 한다. 참고