[BOJ] 9466. 텀 프로젝트 / DFS / Python 풀이

몇 달 전부터 친구랑 같이 문제를 정해서 함께 풀고 있다.

이번에는 친구가 먼저 풀어봤는데 꽤 어려웠다는 문제를 풀어보기로 했다.

 

9466번: 텀 프로젝트

 

백준 9466번 문제로 레벨 골드3에 걸맞는 정답률을 자랑하고 있다.

정답 비율이 23퍼센트밖에 되지 않아서 겁을 먹었지만

풀고 나니 처참한 비율의 이유를 알게 되었다.. 알고 싶지 않았다

 

문제 이해

출처: 백준

문제 설명이 말로 되어 있어서 처음에 이해하기가 어려웠다. 

설명을 여러 번 읽어본 후에야 이해할 수 있었는데, 

결국은 싸이클이 성립될 때 팀이 될 수 있고, 자신을 선택한 경우에도 싸이클로 본다.

여기에서 중요한 점은 출력값이 팀에 속하지 못한 학생의 수라는 것이다.

 

접근

문제를 이해하고 나니까 바로 그래프를 탐색하는 방식을 떠올랐다.

그래프를 어떻게 그리지?를 잠깐 고민했지만 입력 받은 순간 그래프가 완성되어 있더라.

 

처음에는 생성되는 팀의 개수를 출력하는 것으로 착각하고

그냥 인덱스 탐색 하면서 반복문 중첩하려고 했는데 코드가 안 떠올라서..

힌트를 봤다.

나에게 힌트란 ...

백준 로그인하면 보이는 알고리즘 분류

 

사실 감도 안 올 때 계속 고민하면 시간낭비가 맞다.

그래도 저 보기를 클릭하기가 엄청 고민된다.

 

풀이

dfs로 너무 쉽게 풀려서 코드 설명이 따로 필요 없을 정도 ..

다음에 탐색하는 노드가 tmp안에 있으면 거기부터 마지막 요소까지 싸이클을 이루는 것이기 때문에

cnt에 cycle 길이를 더해놓고 마지막에 학생 개수에서 cnt를 빼는 방식으로 풀었다.

import sys
sys.setrecursionlimit(10**7)

def dfs(i):
    global cnt
    
    tmp.append(i)
    visited[i] = True
    nxt = arr[i]
    
    if visited[nxt]:
        if nxt in tmp:
            cnt += len(tmp[tmp.index(nxt):])
        return
    else:
        dfs(nxt)
    
T = int(input())
for i in range(T):
    n = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [False] * (n+1)
    cnt = 0
    for i in range(1, n+1):
        if not visited[i]:
            tmp = []
            dfs(i)
    print(n-cnt)

정답 퍼센트 계속 올라가다가 런타임 에러가 떠서 머리가 멍해졌지만

Recursion Error는 재귀 에러로 최대 깊이만 재설정해주면 해결된다.

이 문제의 입력 최대값이 10**6이기 때문에 그것보다 큰 10**7로 설정해주었다.

 

후기

문제가 이렇게 긴 글로 되어 있으면 언제 이해하나 싶다.

알고리즘 많이 접해보면서 푸는 방식을 익히려고 난이도가 높아도 입출력 간결한 문제를 선호했는데

더 다양한 문제를 풀어보면서 문제 이해와 접근을 빠르게 할 수 있도록 연습해야겠다.