백준 9466 [텀 프로젝트] 파이썬

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

 

생각보다 복잡했다..

 

#백준 9466 텀 프로젝트
import sys
sys.setrecursionlimit(10**7)
T=int(sys.stdin.readline())

def dfs(i):
    if not visited[picks[i]]:
        path.append(picks[i])
        visited[picks[i]]=True
        dfs(picks[i])
    elif picks[i] in path:
        global count
        count+=len(path[path.index(picks[i]):])
        return

for _ in range(T):
    N=int(sys.stdin.readline().rstrip())
    picks=[0]+list(map(int,sys.stdin.readline().split()))
    ans=N
    student_pick=dict()
    for i in range(1,N+1):
        student_pick[i]=picks[i]
    visited=[False] *(N+1)
    count=0 
    for i in range(1,N+1):
        if not visited[i]:
            visited[i]=True
            path=[i]
            dfs(i)
    print(ans-count)

다른곳에서 타고가다가 사이클이 만들어지면 그때도 처리해주는 것이 중요한 문제였다.

EX) 2-> 3-> 4-> 5-> 3 인 경우 2,3,4,5 를 전부 방문처리

 

2에서 시작했다고 방문처리 안하면 안됨. (시간초과 발생)

 

갈 길이 멀다..

 

깔끔하게 정리된 GPT의 코드를 첨부한다.

 

import sys
sys.setrecursionlimit(10**6)  # 깊이 제한을 10^6으로 설정 (10^7은 불필요)
input = sys.stdin.readline

def dfs(node):
    global count
    visited[node] = True  # 방문 처리
    path.append(node)  # 경로에 추가
    next_node = picks[node]  # 다음 학생 번호

    if not visited[next_node]:  # 아직 방문하지 않았다면 계속 탐색
        dfs(next_node)
    elif next_node in path:  # 사이클이 발생한 경우
        count += len(path[path.index(next_node):])  # 사이클 길이만큼 팀을 이루는 학생 추가

    finished[node] = True  # 탐색 완료 처리
    path.pop()  # 백트래킹 (경로에서 제거)

T = int(input())
for _ in range(T):
    N = int(input())
    picks = [0] + list(map(int, input().split()))  # 학생들의 선택 리스트 (1-based index)

    visited = [False] * (N + 1)  # 방문 여부 체크
    finished = [False] * (N + 1)  # 탐색 완료 여부 체크
    count = 0  # 팀을 이루는 학생 수

    for i in range(1, N + 1):
        if not visited[i]:  # 아직 방문하지 않은 노드라면 탐색 시작
            path = []
            dfs(i)

    print(N - count)  # 팀을 이루지 못한 학생 수 출력

물론 위의 코드에도 불필요한 부분이 몇가지 있다.