백준 #9466 텀 프로젝트

내 코드

import sys
# sys.stdin = open("input.txt")
sys.setrecursionlimit(10**6)

def dfs(x, ls):
    global cnt
    visited[x] = True
    if not visited[team[x]]:
        ls.append(team[x])
        dfs(team[x], ls)
    else:
        try:
            left = ls.index(team[x])
            right = len(ls)
            cnt += (right - left)
            return
        except:
            return

T = int(input())
for _ in range(T):
    n = int(input())
    arr = [0] + list(map(int, input().split()))
    team = [i for i in range(n + 1)]
    for i in range(1, n + 1):
        team[i] = arr[i]
    visited = [False] * (n + 1)
    cnt = 0
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i, [i])
    print(n - cnt)

참고 코드

# 참고 코드 kckc0608님
import sys
# sys.stdin = open("input.txt")
from collections import deque

T = int(input())
for _ in range(T):
    n = int(input())
    arr = [0] + list(map(int, input().split()))
    counts = [0 for _ in range(n + 1)]
    for i in range(1, n + 1):
        counts[arr[i]] += 1

    q = deque()
    for i in range(1, n + 1):
        if counts[i] == 0:
            q.append(i)
            counts[i] -= 1
    answer = 0

    while q:
        cur = q.popleft()
        answer += 1
        counts[arr[cur]] -= 1
        if counts[arr[cur]] == 0:
            q.append(arr[cur])

    print(answer)

풀이

처음에 시간초과 두번 먹고나서 의지를 잃었다…ㅎㅎ 하지만! 중꺾마!

3일정도 지나서 다시 도전했당. visited를 매번 초기화 해줄 필요 없이 쭉 진행하면서

사이클이 완성되는 구간을 try except로 찾아내어 정답을 도출 했다.

다른 분들의 풀이를 보다가 deque로 간단하게 푸신 분이 있어서 나도 따라해봤다.

위상정렬 알고리즘의 indegree 방식과 비슷한 느낌이다! 역시 똑똑하신 분들은 많다.

포스팅을 작성하다가 2월에서 3월로 바뀐걸 보고 시간은 참 빠르다는 생각이 든다.

다음주는 부스트캠프가 시작되는 주이다. c++ 공부를 하려고 책도 두권이나 사놓았는데..

시간은 기다려주지 않는다. 열심히 하자!