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

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

9466번: 텀 프로젝트

# DFS로 '사이클'을 찾으면 되는 문제이다.

   코테나 다른 그래프 문제중에 사이클을 찾는 문제들을 자주 볼 수 있는데, 생각보다 코드로

   구현하기 힘들다. 재귀가 함수 안에서 함수를 계속 부르고 그런것이 가시적이지 않아서 그런 것 같다.

   쨋든, 사이클을 찾는 방법은 자주 쓰이니 이해하고 외워두는 것이 좋다!

 

# 배열의 인덱스는 0부터 시작하기 때문에 편하게 숫자를 보기위해 graph에 [0]을 맨앞에 선언하고

   리스트를 입력받아준다. visited배열과 team이라는 set을 초기화시켜주고

   1번 학생부터 N번학생까지 반복문을 돌며 visited[i]가 False이면 dfs(i)를 실행한다.

 

   * dfs함수: x번 학생이 선택항 학생을 i라고 하자. visited[i]가 False이면 dfs(i)를 실행한다.

                 visited[i]가 True이면 i번 학생이 team안에 있는지 확인한다. i가 team안에 없다면

                 nxt = i로 설정하고, nxt가 x가 될때까지 cnt를 1증가시키고, nxt에 nxt가 가리키는 학생을 넣어준다.

                 

                 즉, 사이클에 속한 학생들 수만큼 cnt가 증가하게 된다. 처음에 x번 학생도 사이클에 속하므로

                  while문을 벗어날때 cnt를 1 증가시켜주고 team에 x를 add해준다.

 

# 1번 학생부터 N번학생까지 모두 dfs함수를 돈 뒤 cnt에는 팀이 결성된 학생 수가 들어있으므로

    n에서 cnt를 빼주면 팀에 속하지 않은 학생 수가 나오게 된다.

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
T = int(input())

def dfs(x):
    global cnt
    visited[x] = True
    i = graph[x]
    if not visited[i]:
        dfs(i)
    else:
        if i not in team:
            nxt = i
            while nxt != x:
                cnt += 1
                nxt = graph[nxt]
            cnt += 1

    team.add(x)

for _ in range(T):
    n = int(input())
    graph = [0] + list(map(int,input().split()))
    visited = [False] * (n+1)
    team = set()

    cnt = 0
    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)

    print(n - cnt)

(solved.ac 티어: 골드 3)

 

# pypy3는 빠르지만, 재귀에 약하다

  (sys.setrecursionlimit가 안먹어서 이런문제를 풀 때 pypy로 제출하면 메모리초과나 RecursionError가 뜬다.)

 

# set에서 in함수는 O(1)이다.