[백준 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  
from collections import deque  

def solution():  
    T = int(input())  
    for _ in range(T):  
        N = int(input())  
        nums = [0] + [*map(int, input().split())]  
        # 이미 그룹이 있는지 체크  
        group = [False] * (N+1)  
        result = N  
        # 문제 핵심은 그룹이 되려면 처음 선택하는 사람이 => 마지막에 선택당해야 됨  
        # 그래프를 만들어나가야 됨        
        for i in range(1, N+1):  
            if not group[i]:  
                st = [i]  
                while True:  
                    # 방문 처리해주고  
                    # 이미 방문한 적있다면 => 현재 그룹만드는 중에 선택된 사람이라면                    
                    # 전체 길이에서 그래프를 못이룬 길이만큼 빼주면된다.                    
                    group[st[-1]] = True  
                    if group[nums[st[-1]]]:  
                        if nums[st[-1]] in st:  
                            result -= len(st) - st.index(nums[st[-1]])  
                        break  
                    st.append(nums[st[-1]])  
        print(result)  
solution()