[백준(BOJ)] 9466번 : 텀 프로젝트 - PYTHON[파이썬]

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

9466번: 텀 프로젝트

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

자기 자신을 선택하면 혼자 팀을 구성할 수 있고, 원을 이루어 모든 사람이 선택되면 모든 학생들이 동일한 팀을 꾸릴 수 있다.

 

즉, 조건은 사이클이다.

 

사이클이 생기면 팀이 생기는데 사이클 판별을 dfs로 해주었다.

 

---

 

⊙ 문제 풀이

 

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

K = int(input())


def dfs(n):
    global result
    visited[n] = 1
    trace.append(n)
    num = team[n]

    if visited[num]:
        if num in trace:
            result += trace[trace.index(num):]
        return
    else:
        dfs(num)


for _ in range(K):
    N = int(input())

    team = [0] + list(map(int, input().split()))
    visited = [0 for _ in range(N+1)]
    result = []
    for i in range(1, N+1):
        if not visited[i]:
            trace = []
            dfs(i)
    print(N-len(result))

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!