스파르탄 365 5주차 (4) 텀 프로젝트

참고 사이트: live the life you love

5주차

백준 9466번 텀 프로젝트

문제링크 : https://www.acmicpc.net/problem/9466

💡 풀이 중 고민

• 좌우로 어떻게 탐색을 할 것인가
• dict 형으로 받고 싶은데 (연결리스트) -> dfs로 가자

! 해결 방법

• 사이클을 찾는 방식으로 간다.
  반드시 team의 마지막 학생은 team의 첫 학생을 지목해야한다.
• 런타임 에러
  : sys.setrecursionlimit(111111) 코드를 추가해서 해결

!! 스킬

if not done[next]: #사이클이 형성되었다.
students = list(map(lambda x : int(x)-1, input().split()))
visited = [False]*n

람다 사용법

깨달음

• 잊지말자: dfs에서 방문 처리 먼저 하고 조건대로 가기

풀이

import sys
sys.setrecursionlimit(111111)
input = sys.stdin.readline

t = int(input())

def dfs(cur):
    global cnt, visited, done
    # 방문처리
    visited[cur] = True
    next = students[cur]
    print(next)
    if not visited[next]:
        dfs(next)
    else:
        if not done[next]: #사이클이 형성되었다.
            i = next
            while i != cur: #팀원 카운트
                cnt += 1
                i = students[i]
            cnt += 1 # 플러스 본인
    done[cur] = True

for _ in range(t):
    n = int(input())
    students = list(map(lambda x : int(x)-1, input().split()))
    visited = [False]*n
    done = [False]*n # 팀 매칭 여부 = 사이클 여부
    cnt = 0
    for i in range(n):
        if not visited[i]: #방문을 안했다면
            dfs(i)
    print(n-cnt)