백준 9466 텀 프로젝트 파이썬 풀이

난이도 : 골드3

풀이일 : 2401281

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

9466번: 텀 프로젝트

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys
from collections import deque


# 사이클 확인
def iscycle(n):
    # 지목된 학생들
    team = dict()
    team[n] = 0
    queue = deque([(n, 0)])
    check[n] = True
    while queue:
        x, idx = queue.popleft()
        # 현재 학생이 지목한 학생
        nx = arrow[x]
        # 지목한 학생이 이미 팀에 있을 경우
        if nx in team:
            return len(team) - team[nx]
        # 지목된 학생이 팀에 없을 경우
        if not check[nx]:
            team[nx] = idx + 1
            queue.append((nx, idx + 1))
            check[nx] = True

    # 사이클이 아니면 0명 반환
    return 0


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

for tc in range(T):
    N = int(sys.stdin.readline())
    # 지목하는 학생 정보
    arrow = [0] + list(map(int, sys.stdin.readline().split()))
    # 사이클 판별 여부
    check = [False] * (N + 1)
    # 팀을 이루지 못한 학생 수
    alone = N

    # 사이클로 판별되지 않은 학생에 대해 판별 함수 실행
    for i in range(1, N + 1):
        if not check[i]:
            # 전체 학생수에서 팀을 이룬 학생 수 차감
            alone -= iscycle(i)

    print(alone)

• arrow : 각 인덱스의 학생이 팀이 되길 희망해 지목하는 학생 정보
• check : 해당 인덱스 학생이 팀을 이룰 수 있는지 검사 수행 여부
  • 시간초과를 피하기 위해, 한 번이라도 iscycle 내에서 검사했지만 팀을 이루지 못한 학생은 제외하기 위한 목적
• alone : 처음에는 모든 학생 수에서 시작해, 팀을 이루는 학생들은 제외하고 팀을 이루지 못한 학생의 수를 출력
• iscycle : 사이클을 이루는지 검사하는 함수
  • team : 원래는 list를 사용해 동일한 로직을 올리면 76%? 78% 정도에서 시간초과로 오답처리가 되어 딕셔너리로 속도 개선
    • '학생번호 : 인덱스' 형태로 저장
  • queue : team 딕셔너리에 사용하기 위해 현재 학생, 인덱스를 함께 저장
  • 현재 학생에게 지목된 학생이 이미 팀에 있다면, 지목된 학생부터 현재 학생까지가 팀 -> 전체 길이 - 지목된 학생 전 학생 수
  • 현재 학생에게 지목된 학생이 팀에 없다면, 해당 학생과 인덱스 정보를 queue, team에 추가

---

느낀점

• 엄청 오래전부터 도전하고 엄청 틀려왔던 문젠데 풀어내서 기분 좋다. 시간을 개선할 방법을 조금씩 더 머리를 짜내가면서 찾고 있는데, 이제는 더 이상 미룰 수 없어서 시간복잡도도 공부를 해봐야 할 것 같다.
• 오늘은 결국 풀어내서 파이썬 알고리즘을 올릴 수 있는 날!