[Python] 백준 9466번 - 텀 프로젝트 (골드 3)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - DFS

 

https://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까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

---

 

처음엔 dfs를 통해 반복 방문한 노드를 찾아서 계산하는 방식으로 코드를 작성했으나 풀지못했고 이를 해결할 방안을 생각해내지 못했다.

 

(오답 코드)

import sys
input = sys.stdin.readline

T = int(input())

def dfs(now, depth):
    if depth == 0 and check[data[now]] == 1:
        return
    if check[data[now]] >= 2:
        return
    check[data[now]] += 1
    dfs(data[now], depth+1)

for _ in range(T):
    n = int(input())
    data = [0]+list(map(int, input().split()))
    check = [0] * (n+1)
    
    for i in range(1, n+1):
        #if check[i] == 0:
        dfs(i, 0)
            
    #print("A:",check.count(1)+check.count(0)-1)
    print(check.count(1)+check.count(0)-1)

 

너무 단순하게 생각한 탓인가 더 좋은 해법을 찾지 못했다.

 

---

 

Chat GPT의 도움을 받아 문제를 해결해보려 했으나 답을 찾지 못했고 큰 도움을 받아서 겨우 해결했다...

 

이 문제를 다시한번 풀라고하면 같은 방식을 떠올리지 못할 것 같다.

 

나중에 꼭 다시 풀어보고 내것으로 만들어야 할 문제인것 같다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(x):
    global result
    visited[x] = 1 # 방문 중 상태로 표시
    next_node = data[x]
    
    if visited[next_node] == 0: # 다음 노드를 아직 방문하지 않았다면
        dfs(next_node)
    elif visited[next_node] == 1: # 사이클이 발생한 경우
        student = next_node
        while student != x: # 사이클에 포함된 학생 수 세기
            result += 1
            student = data[student]
        result += 1 # 현재 노드도 사이클에 포함됨
    
    visited[x] = 2 # 방문 완료 상태로 표시

T = int(input())
for _ in range(T):
    n = int(input())
    data = [0] + list(map(int, input().split()))
    visited = [0] * (n + 1)
    result = 0

    for i in range(1, n + 1):
        if visited[i] == 0: # 아직 방문하지 않은 노드에 대해서만 DFS 실행
            dfs(i)
            
    print(n - result) # 사이클에 속하지 않는 학생 수 출력

 

visited - 0 : 미방문

visited - 1 : 방문 중

visited - 2 : 방문 완료

 

위와 같이 표기하고

 

예제 1을 예제로 살펴보면

 

1
7
3 1 3 7 3 4 6

 

방문하지 않은 노드를 방문처리하며 dfs로 재귀하는것 까지는 쉽다.

 

이후 visited - 1 (방문중)일 경우 사이클이 발생한 것으로 간주하여

 

현재 위치의 값부터 다시 재귀를 하듯이 while문을 통해 사이클이 생기는 부분을 역추적하여 result += 1씩 추가한다.

 

만약 해당 문제가 사이클이 생기는 곳만 찾는 문제였다면 result+1이 되는 구간을 따로 저장하면 되는 것이다.

 

생각을 깊이해야 하는 문제였거나, DFS경험이 많다면 풀만 한 문제라고 생각한다.