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

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

9466번: 텀 프로젝트

 

# 조건

• 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다.
• 프로젝트 팀원 수에는 제한이 없다.
• 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다.
• 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 
• 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
• 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

 

• 위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
• 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다.
• 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

 

# 접근 방법

• 우선 학생 수를 크기로 하는 배열 arr을 생성해준다.
• 해당 번호의 학생이 선택한 번호를 간선으로, dfs를 돌려준다.
• 시작 학생의 번호로 돌아오는 사이클이 있는지 구해주면 된다.
• visited 배열을 만들어 주어 시작점의 학생을 True로 변경해준 후 dfs 시작한다.

 

시간 초과

 

• 4 7 6 이 팀이 되는 경우 4번에서 이미 사이클이 성립되었으므로 6번과 7번에서 중복 카운트가 되면 안된다. (visited 배열로 해결)
• 프로젝트 팀에 속하지 못한 학생들의 수를 구해야 하므로, 해당 사이클에 포함되는 학생 수를 기록해준다.
• 사이클을 도는 동안 빈 배열에 학생 번호를 추가해준 후, 사이클이 성립되지 않으면 visited에서 False로 변경해준다. -> 시간초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
# 시작 인자 받아주기  
def dfs(start):  
    global result  
    stack = [start]  
    cnt = 0  
    re_visited = []  
    while stack:  
    
        cnt += 1  
        cur_student = stack.pop()  
        if selec[cur_student] == start:  
            result -= cnt  
            break  
        elif not visited[selec[cur_student]]:  
            stack.append(selec[cur_student])  
            re_visited.append(selec[cur_student])  
            visited[selec[cur_student]] = True  
  
    for i in re_visited:  
        visited[i] = False  
  
T = int(input())  
for _ in range(T):  
    n = int(input())  
    selec = [0] + [*map(int, input().split())]  
    result = n  
  
    visited = [False for _ in range(n+1)]  
    for i in range(1, n+1):  
        visited[i] = True  
        dfs(i)  
  
    print(result)

 

해결 방법 및 Solution

• 우선 이미 방문한 정점을 다시 방문하지 않도록 조건문을 달아주었다.
• 방문을 할 때 True로 변경해주고, stack에 담아준다.
• stack 에 현재 학생이 지목한 번호가 들어있고 방문을 한 적이 있다면 == 사이클 존재 가능성
• 이 때, 스택의 길이에서 -> 싸이클이 시작하는 번호의 인덱스를 빼주면 된다..
• 핵심은 마지막 번호의 사람은 처음 시작한 번호를 지목한다는 점!!
  • 1 2 3 4 5 3의 경우 전체 길이 5 - ( 3의 인덱스 )-> 2 = 3이 사이클의 길이
  • 마지막에 전체 인원수 - result를 통해 답을 도출

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
# 시작 인자 받아주기  
def dfs(start):  
    global result  
    stack = [start]  
    while True:  
        visited[stack[-1]] = True  
        if visited[selec[stack[-1]]]:  
            if selec[stack[-1]] in stack:  
                result += len(stack) - stack.index(selec[stack[-1]])  
            break  
        stack.append(selec[stack[-1]])  
  
  
  
T = int(input())  
for _ in range(T):  
    n = int(input())  
    selec = [0] + [*map(int, input().split())]  
    result = 0  
  
    visited = [False for _ in range(n+1)]  
    for i in range(1, n+1):  
        if not visited[i]:  
            stack = [i]  
            dfs(i)  
  
    print(n-result)