📚 9466 - 텀 프로젝트

텀 프로젝트

 

풀이

• 파이썬에서 색다른 점들을 공부했다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 이게 무엇인가 뜻하면은?

• 혼자인 경우는 자기 자신을 뽑고
• s1 → s2 → s3 → s4 → s5 → ~ → sn → s1 (자기자신에게 돌아온다.)

 

ex)

1	2	3	4	5	6	7
3	1	3	7	3	4	6

➡️ 여기서 (4, 7, 6)이 사이클이다.

 

이문제는 순열 사이클에서 업그레이드된 문제인 것 같다.
(진짜 까다로운게 많이 추가된 느낌)

참고한 사이트를 이용하여 문제를 풀었다.

✔️ 어떻게?

• 일단 배열 1번부터 n번까지 인덱스를 돌린다.
• 돌리면서 아직 방문하지 않은 index가 발견되면 거기서부터 깊이우선탐색을 돌린다.
  • 현재 인덱스부터 시작하는 노드부터 연결된 dfs에서 가장 마지막 index가 가리키는 노드가 다시 처음 노드를 가리킨다면? → 이는 사이클이다. ( 4 → 7 → 6 → 4 )

 

⚠️ 주의할 점
재귀함수를 사용할 때 sys.setrecursionlimit(111111) 이를 사용하는데, 이는 Python은 기본적으로 재귀 깊이 제한이 매우 낮기 때문에 sys.setrecursionlimit(111111)를 통해 깊이를 늘려줘야 한다. (재귀 사용했는데 이거 안넣을시 이 문제 런타임 오류 발생함)

 

소스

• 방문한 곳이면 cycle에 현재 방문한 것이 담겨있는지(첫 시작점인지) 확인한다.
• 방문하지 않았으면 cycle에 담는다.

from sys import stdin as s

import sys

sys.setrecursionlimit(111111)
# 파이썬은 기본적으로 재귀 깊이 제한이 매우 낮기 때문에 늘려줘야 한다.

t = int(s.readline())


def dfs(start):
    global result
    visited[start] = True
    cycle.append(start)
    next = graph[start]

    if visited[next]:
        if next in cycle:
            result += cycle[cycle.index(next):]  # next가 시작 점 : 문제에서 보면 4 -> 7 -> 6에서 4가 시작점이라면, 시작점 인덱스 시작부터 끝까지(사이클)
        return
    else:
        dfs(next)


for _ in range(t):
    n = int(s.readline())
    graph = [0] + list(map(int, s.readline().split()))
    visited = [True] + [False] * n
    result = []
    for i in range(1, n + 1):
        if not visited[i]:
            cycle = []
            dfs(i)

    print(n - len(result))

 

채점 결과

 

---

참고

• https://claude-u.tistory.com/435