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

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

9466번: 텀 프로젝트

이 문제를 풀 때

가장 어려웠던 부분은

사이클 구현에 대한 것입니다.

DFS로 길찾기까지는 어느정도 이해가 가는데

그래서 어떻게 사이클을 만들지?

라는 고민이 들었습니다.

저는 root라는 것이 나오면

사이클이 있다고 판단하는 코드를 만들었습니다.

예를들면

1이 처음에 들어오면 root로 설정하고

이후에 1이 들어오면

사이클이 완성이 되었다고 판단하도록 만들었습니다.

그런데 이 방식은

위의 예시같은 경우에는

사이클로 보지 않고 지혼자 계속 돌다가

시간초과를 만들 수 있었습니다.

# 백준 9466 팀 프로젝트


def dfs(num, root):
    global down
    now = student[num] - 1
    down.append(num)

    if now == root:
        for p in down:
            visited[p] = 1
        return
    else:
        if now not in down:
            dfs(now, root)


T = int(input())
for _ in range(T):
    n = int(input())
    student = list(map(int, input().split()))
    visited = [0] * n
    for i in range(n):
        if visited[i] == 0:
            up = []
            down = []
            dfs(i, i)

    print(visited.count(0))

이런 식으로 제출했더니

33%대에서 시간초과가 떴습니다.

계속 고민하다가 구글링을 참고해서

코드를 수정했습니다.

#백준 9466 팀 프로젝트
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(num):
    #down 이라는 리스트에 현재 num을 넣어준다
    global result
    now=student[num]-1
    #now는 현재 num의 학생이 가리키는 숫자
    down.append(num)
    visited[num]=1
    #만약에 지금 갈려는 곳을 이미 방문했다면
    if visited[now]==1:
        #방문한 곳이 리스트에 있다면 넣어준다. now가 있는 곳부터 쭉 result에 넣어준다.(사이클을 넣어준다는 것)
        if now in down:
            result+=down[down.index(now):]
        return

    else:
        #그게 아니라면 경로 더 돈다
        dfs(now)


T=int(input())
for _ in range(T):
    n=int(input())
    student=list(map(int,input().split()))
    visited=[0]*n
    result=[]
    for i in range(n):
        if visited[i]==0:
            down=[]
            dfs(i)


    print(n-len(result))

 

재미있는 사실은

pypy3로 제출하면 메모리초과가 뜨고

python3로 제출해야 통과가 됩니다.

이 코드를 보면

down이라는 리스트에

현재까지 이동한 학생들을 받아줍니다.

그리고 다음에 이동할 학생이

이미 visited가 완료가 된 상태라면

down에 있는지 확인합니다.

down에 있다면 현재 사이클을 돌면서 나온 친구라는 의미.

그렇다면 사이클 안에 있는 것이고

사이클은 순차대로 받을 것이니

그 친구가 있는 것부터 뒤까지 싹다 result에 추가해줍니다.

 

https://tooo1.tistory.com/m/505

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

https://honggom.tistory.com/122

[백준] 9466번 문제 (텀 프로젝트) 파이썬(Python) 풀이

참고한 문헌입니다.

어떻게 하면 사이클을 판단할 수 있는지

공부하게 만들어준 좋은 문제였습니다.