[BOJ] 9466. 텀 프로젝트(Python) / DFS

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

꽤 까다로웠던 DFS 문제였다.

 

각 학생이 함께 프로젝트 하고 싶은 사람들 지목하고 지목을 한 사람들끼리 사이클을 이루는지 여부를 파악하여

팀을 이루지 못한 학생들의 수를 계산해야 한다.

• DFS를 이용하여 1번 학생부터 n번 학생까지 방문표시하며 지목한 다음 학생의 번호를 차례대로 확인한다.
• 이 때, 사이클 리스트에 넣는데, 다음 숫자가 이 리스트에 있다면 사이클 이루는 경우이므로,
• 전체 학생의 수에서 사이클을 이루는 학생의 수를 빼준다.

기본적인 DFS 틀에서 조건을 잘 걸어주어 학생 번호가 사이클 이룰 때 구하는 결과값에 반영해주는 것이 핵심이었다.

 

 

파이썬 코드는 다음과 같다.

---

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)    # 재귀 깊어지는 경우 오류 방지

def dfs(x, cycle):
    global ans
    visited[x] = 1
    cycle.append(x)     # 사이클 이루는지 확인하기 위함
    nx = numbers[x]     # 현재 번호가 가리키는 다음 번호

    if visited[nx]:
        if nx in cycle:     # 사이클 이룸
            # 사이클 이루는 부분의 갯수 전체 갯수에서 빼줌
            ans -= len(cycle) - cycle.index(nx)
            return
    else:
        dfs(nx, cycle)

T = int(input())
for _ in range(T):
    n = int(input())
    numbers = [0] + list(map(int, input().split()))
    visited = [0] * (n+1)
    ans = n
    for i in range(1, n+1):     # 차례대로 확인하며
        if not visited[i]:      # 방문하지 않은 곳이라면 dfs로 사이클 만들기
            dfs(i, [])
    print(ans)

---

• 시간 : 1512ms / 409980KB
• 고찰 : 문제 이해하는 데 한참 걸렸다.. 난독증 먼저 고치자ㅠㅠ 문제를 빠르게 파악하고 정확하게 이해한 후 코드를 설계하는 것이 중요하다.