백준 - 9466번(DFS, cycle 생성)

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

9466번: 텀 프로젝트

import sys

sys.setrecursionlimit(111111)

def dfs(x):
    global result
    visited[x] = True
    cycle.append(x)

    if visited[arr[x]] == True:
        for i in range(len(cycle)):
            if arr[x] == cycle[i]: 
                result = result - (len(cycle) - i)
                break
        return 1
    else:
        dfs(arr[x])

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    arr = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [False for _ in range(n+1)]
    result = n

    for i in range(1, n + 1):
        if visited[i] == False:
            cycle = []
            dfs(i)

    print(result)

우선 이 문제는 시작점에서 연결된 조건에 따라서 다른 점으로 타고 가는 형식이다.

BFS를 사용하지 않고 DFS를 사용하는 이유는 최단거리나 시간을 찾는 것이 아니고 주어진 조건에 따라서 깊이 탐색을 하기 때문이다.

결론적으로 전체탐색을 해야 하는데 주어진 데이터의 값이 클 때는 DFS가 유리하다.

 

우선 visited가 fasle 일때만 dfs 탐색을 실행한다.

cycle에 탐색한 학생들의 값들을 모두 넣어준다.

만약 1 -> 2 -> 4 -> 3 -> 2 이렇게 될 경우 1을 제외한 2,4,3 학생들이 한 팀이 된다. 2,4,3으로 순환 그래프가 하나 만들어 지기 때문이다.

1의 경우 다른사람의 선택을 받더라도 이미 위와 같은. 사이클로 간다는 사실이 보였다. 그래서 1은 혼자 하게 된다.

 

따라서 도달한 arr[x]가 전에 방문한 적이 있는 경우 사이클을 만들어준다.

cycle 배열을 돌면서 arr[x]가 있는 지점부터 끝까지가 하나의 사이클이 된다.

따라서 전체 학생수에서 팀을 이룬 학생수를 빼주면 된다.

이를 반복하면 정답을 구할 수 있다.