[백준] 9466 텀 프로젝트(GOLD 3 - Python)

 

 

해당 글에서는 텀 프로젝트 문제를 Python을 이용해 풀이하고자 한다.

9466번: 텀 프로젝트

 

 

원래는 이 문제를 풀 생각이 아니었지만, 아래에 있는 Union-Find를 통해 무방향 그래프의 사이클을 구하는 알고리즘에 대해 공부하다가, 방향 그래프에서 사이클을 구하는 방법이 궁금해져 찾아보다가 해당 문제를 풀게 됐다.

[알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기

 

 

🔷 문제 설명

 

🔷 문제 풀이

1️⃣ 풀이 방법

해당 풀이에서는 사이클을 구하는 방법에 대해 알아야 한다. 예제를 통해 이에 대해 알아보자.

 

예제

다음의 테스트 케이스를 통해 사이클을 구하는 방법에 대해 이해해 보자.

• n = 3, 학생들의 번호 = [2, 3, 2]
  즉, 3명의 학생이 존재하며, 1은 2를, 2는 3을, 3은 2를 가리키므로, 아래와 같은 그래프가 형성된다.

이제 위 그래프에서 사이클을 구하는 방법에 대해 알아보자.

노드 1부터 탐색하여 사이클을 구해보자. 이때 방문한 노드를 순서대로 저장하는 리스트를 cycle이라고 하자.

 

✔ 노드 1 방문

아직 방문되지 않은 상태이므로, visited[1] = True로 변경해준다.
노드 1에 방문했으므로, cycle에 1을 추가해준다.

• cycle = [1]

이후 1이 가리키는 2를 동일한 방식으로 방문한다.

 

✔ 노드 2 방문

아직 방문하지 않은 상태이므로 visited[2] = True로 변경한다.

이후 cycle에 추가한다.

• cycle = [1, 2]

동일하게 2가 가리키는 3에 대해서도 똑같이 반복한다.

 

✔ 노드 3 방문

아직 방문하지 않은 상태이므로 visited[3] = True로 변경한다.

이후 cycle에 추가한다.

• cycle = [1, 2, 3]

이후 3이 가리키는 2에 대해 다시 반복한다.

 

✔ 노드 2 방문

이때, 노드 2는 앞서 방문한 상태(visited[2]가 True)에 해당한다. 그러므로 사이클이 발생했을 가능성이 존재하게 된다.

사이클 내에 존재하는지 알아보기 위해 cycle에 존재하는지 알아보자.

• cycle = [1, 2, 3]

위 cycle에 대해 2가 존재하므로, 이번 dfs에서 사이클이 발생한 것이다.

따라서 cycle에서 2부터 끝까지 리스트를 슬라이싱 하면 해당 리스트가 사이클의 순서를 나타내는 리스트인 것이다. 해당 예제에서는 [2, 3]이 된다.

 

2️⃣ Python 풀이

위에서 설명한 방식을 기반으로 풀이한 코드가 다음 코드이다.

 

모든 노드에 대해서 설명과 같이 사이클을 찾고 사이클을 나타내는 리스트를 result에 모두 저장한 후, 마지막에 전체 학생 개수에서 result에 존재하는 노드 개수를 세면 된다.

result += cycle[cycle.index(nxt):] # nxt가 존재하는 부분부터 끝까지, 사이클 집합에 추가

 

전체 코드

import sys
read = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(n, result): # 사이클을 찾는 함수

    visited[n] = True # 방문 처리
    cycle.append(n)

    nxt = person[n]
    if visited[nxt]: # 방문한 경우
        if nxt in cycle: # 이번 사이클에 존재하는지 확인. 사이클 내에 존재하는 경우
            result += cycle[cycle.index(nxt):] # nxt가 존재하는 부분부터 끝까지, 사이클 집합에 추가
    
    else: # 방문하지 않은 경우
        dfs(nxt, result) # nxt에 대해 사이클 찾기

for _ in range(int(read().strip())):
    n = int(read().strip())
    person = [0] + list(map(int, read().split()))
    visited = [False] * (n+1)

    result = [] # 사이클이 존재하는 학생들의 집합
    for i in range(1, n+1):
        if not visited[i]: # 방문하지 않은 경우
            cycle = [] # 사이클을 저장할 리스트
            dfs(i, result)
    
    print(n-len(result))