[백준] 9466번 텀 프로젝트 _ Python

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

9466번: 텀 프로젝트

 

 

---

 

1. Preview

시간 복잡도: O(N)

 

공간 복잡도: O(N)

 

유형: 그래프 탐색, dfs

---

 

2. 초기 접근 방법

 

그래프 탐색을 하면서 자기자신을 만날 때, 즉 사이클이 형성이 되어야 한 팀이다.

def dfs(start, x):
    for k in graph[x]:
        if not visited[k]:
            visited[k] = True
            judge.append(k)
            dfs(start, k)

    if visited[start]: # 팀 결성 o
        return True
    else: # 팀 결성 x
        return False
        
        
if __name__ == "__main__":
    for i in range(1, len(want)):
        judge = []

        # 사이클 판단
        if not bfs(i):
            notTeam += 1
            for j in judge:
                visited[j] = False

 

일단 팀 결성 유무에 관계없이 방문 처리를 하고

팀 결성 되었을 시 → 방문 유지

팀 결성이 되지 않았을 시 → 방문했던 것을 False로 초기화 한다.

 

 

---

 

3. 생각

위 접근법으로 풀었을 때 '시간초과'를 받았다.

팀 결성이 되지 않았을 시 → 방문했던 것을 False로 초기화하는 연산 복잡도는 dfs depth 길이와 같다.

입력받는 학생의 수 범위가 2<=n<=100000 이니 최대 n*(n+1)/2 시간 복잡도가 걸리므로 시간초과가 났으리라 생각된다.

 

 

그럼 어떻게 풀어야 할까??

 

현재 dfs 탐색을 할 때 방문하게 될 노드들을 저장할 cycle_list를 만든다.

기본적으로 미방문 노드일 경우 dfs 탐색을 하게 되고, visited[] 방문을 한다.

하지만 이미 방문했을 경우

   현재 탐색 내에서 재방문 한 노드인지, 즉 사이클이 형성되는지 확인해야 한다.

   사이클이 형성되었을 시, 이전 출발 인덱스부터 끝(현재)까지의 길이(=이 길이는 팀이 형성된 사람 수이다.)를 뺀다.

 

이전 방식은 올바른 사이클을 판단하기 위해서

사이클이 형성되지 않았음에도 True가 되었던 노드들을 다시 False로 바꿔주는 과정이 필요했다.

 

하지만 이 방식에서는 직전 dfs()에서 노드들이 True로 바뀌어도 문제가 없다.

cycle_list 리스트를 통해서 방문했던 노드들이 현재 탐색에서 방문했는지를 판단할 수 있기 때문이다.

 

풀이를 보니 '아!' 싶었다.

매 dfs() 탐색이 독립적으로 사이클 형성을 판단할 수 있게 작성할 수 있구나!

비슷한 문제에서 적용할 수 있도록, 풀이 방법을 잘 기억해두자!!

def dfs(x):
    global result

    visited[x] = True
    cycle_list.append(x)

    # x가 팀을 하고자 하는 사람
    select = want[x]

    # 다음에 갈 노드를 이미 방문한 경우
    if visited[select]:
        # 사이클이 형성 되었을 때
        if select in cycle_list:
            result -= len(cycle_list[cycle_list.index(select):])
        return

    # 미방문 노드일 경우
    else:
        dfs(want[x])

 

 

---

 

4. 코드

import sys
sys.setrecursionlimit(10**6)

def dfs(x):
    global result

    visited[x] = True
    cycle_list.append(x)

    # x가 팀을 하고자 하는 사람
    select = want[x]

    # 다음에 갈 노드를 이미 방문한 경우
    if visited[select]:
        # 다음에 갈 노드가 cycle_list에 있는 경우
        if select in cycle_list:
            result -= len(cycle_list[cycle_list.index(select):])
        return

    # 미방문 노드일 경우
    else:
        dfs(want[x])



T = int(input())
for _ in range(T):
    N = int(input()) # 학생 수
    want = [0] + list(map(int, input().split())) # 각자 지목

    notTeam = 0
    visited = [False for _ in range(N+1)]

    result = N
    for i in range(1, N+1):
        if not visited[i]:
            cycle_list = []
            dfs(i)

    print(result)