새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 9466 텀 프로젝트

by 언호 2022. 7. 2.

📖 문제


🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

학생들이 한명을 선택하여 팀이 이루어지는 경우는 사이클이 이루어지는 경우입니다.

따라서, 학생들을 탐색하며 사이클이 이루어지는 경우를 탐색하면 되었습니다.

 

학생들을 순서대로 탐색하였고, 이미 탐색을 했다면 이후에 같은 학생을 탐색하여도 어차피 같은 결과이므로 한번만 확인하도록 방문 변수를 만들어 확인하였습니다.

2) 알고리즘

  • DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(start):
    stack = [start]             
    pick = []                               # 선택된 학생들

    while stack:
        node = stack.pop()
        if not visited[node]:               # 현재 학생을 확인해보지 않았다면
            visited[node] = 1               # 확인 체크
            pick.append(node)               # 선택된 학생 명단에 추가
            next = selects[node] - 1        # 다음 학생 추가
            stack.append(next)
    
    if next in pick:                        # 선택된 학생 명단에, 다음 학생이 포함되어 있다면
        return pick[pick.index(next):]      # 그 학생을 기준으로 사이클(팀)이 만들어짐
    return []                               # 팀이 안이루어졌으므로 빈 리스트 반환

T = int(sys.stdin.readline())                                   # 테스트 케이스 개수

for _ in range(T):
    N = int(sys.stdin.readline())                               # 학생의 수
    selects = list(map(int, sys.stdin.readline().split()))      # 각 학생별 선택한 학생 번호
    visited = [0] * N                                           # 학생 탐색 여부
    answer = set()                                              # 팀으로 이루어진 학생들 명단
    
    for i in range(N):  
        if not visited[i]:              # 아직 확인해보지 않은 학생일 때
            team = solution(i)          
            answer.update(team)         # 팀으로 이루어진 학생들은 명단에 추가

    print(N - len(answer))

🔗 문제 링크

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

 

9466번: 텀 프로젝트

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을

www.acmicpc.net

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 1516 게임 개발  (0) 2022.07.04
[백준] 11437 LCA  (0) 2022.07.03
[백준] 11559 Puyo Puyo  (0) 2022.07.01
[백준] 3055 탈출  (0) 2022.06.30
[백준] 17281 ⚾  (0) 2022.06.29

댓글