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

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

9466번: 텀 프로젝트

---

시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제.

아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 

 

---

아이디어

1. 그래프

• 일단 보자마자 그래프를 써야 한다고 생각했다.
• 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다.
• 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다.

2. dfs

• 방문 유무를 통해 사이클이 생겼는지 안 생겼는지 찾기로 결정
• 문제 예제에 있는 걸로 설명하면 함수(dfs)에서 4 -> 7 -> 6 방문 후 다시 4로 방문한다.
• 이때 dfs(4)에서 이미 4가 방문되었으면 사이클이라고 판단하고 학생 수를 계산해준다.

 

---

전체 코드

import sys

sys.setrecursionlimit(10**6)

def dfs(n):
    global count

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

    if visited[arr[n]] == True:
        if arr[n] in cycle_list:
            count -= len(cycle_list[cycle_list.index(arr[n]):])
        return

    else:
        dfs(arr[n])

T = int(input())

for _ in range(T):
    N = int(input())

    arr = [0]
    arr.extend([int(x) for x in sys.stdin.readline().rstrip().split()])

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

    print(count)

 

---

코드 설명

T = int(input())

for _ in range(T):
    N = int(input())

    arr = [0]
    arr.extend([int(x) for x in sys.stdin.readline().rstrip().split()])

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

    print(count)

 

입력하는 부분은 간단하다.

arr리스트에서 인덱스는 선택하는 학생 그리고 값은 선택되는 학생으로 저장한다.

dfs는 1부터 N까지 전부 실행하고, 이미 방문된(visited) 노드는 넘긴다.

왜냐, 이미 찾은 사이클을 중복해서 또 찾을 수 있기 때문.

 

def dfs(n):
    global count

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

    if visited[arr[n]] == True:
        if arr[n] in cycle_list:
            count -= len(cycle_list[cycle_list.index(arr[n]):])
        return

    else:
        dfs(arr[n])

먼저 dfs함수를 실행하면 방문 표시를 하고 임시로 만든 사이클 리스트에 노드를 추가해준다.

 

그리고 내가 방문할 다음 노드(arr[n])가 한 번도 방문을 안 했으면 dfs(arr[n]) 실행해준다.

반대로 arr[n]가 이미 방문한 상태라면  arr[n]이 사이클 리스트에 있는지 확인한다.

사이클 리스트에 있다면 전체 학생수에서 사이클 크기만큼 빼주면 된다.

 

사이클 리스트를 슬라이싱하는 이유는 다음과 같다. 

예를 들어 위와 같은 그래프가 있다고 했을 때,

dfs(2)를 실행하면 사이클 리스트에 [2, 4, 7, 6] 이렇게 저장될 것이다.

여기서 사이클은 4 7 6 이므로 사이클이 시작한 4에서부터 리스트를 잘라주면 된다.