[ 백준 9446 ] 텀 프로젝트 - Python

문제 보기

이 문제는 DFS 문제이다.

 

DFS를 구현하는 것은 어렵지 않았으나, 시간 초과를 해결하는 부분이 쉽지 않았다.

 

• 알고리즘
  
  • 1번부터 N번까지 순서대로 탐색을 시작한다.
  • 해당 번호에서 DFS 탐색을 시작한다. (지나간 부분은 같은 팀으로 가정)
  • 위에서 탐색한 방향의 역순으로 탐색하면서 사이클을 확인한다. (-1을 대입)
  • 역순으로 탐색하면서 -1로 채워지지 않은 부분은 팀을 이루지 못한 것이라고 생각하면 된다.

처음에는 역순으로 탐색하지 않고, 팀을 관리하는 별도의 배열을 만들어서 append, in 연산자를 활용하였다. 그 결과 80%에서 시간 초과가 발생하였다. 시간을 절약하면서 최소한의 탐색을 할 수 있는 방법이 무엇이 있을까 생각해보니 역순으로 탐색하는 방법이었다.

코드

import sys

sys.setrecursionlimit(10 ** 6)


if __name__ == "__main__":

    T = int(input())
    for _ in range(T):
        N = int(input())
        p = list(map(int, input().split()))
        p.insert(0, 0)  # 인덱스 편의를 위해서 삽입
        team = [0] * (N + 1)

        for i in range(1, N + 1):
            if team[i] == 0:  # 아직 팀이 없는 경우
                team_number = i
                # 팀 구성한다고 가정
                while team[i] == 0:
                    team[i] = team_number
                    i = p[i]
                # 역순으로 순환하면서 사이클 확인
                while team[i] == team_number:
                    team[i] = -1
                    i = p[i]
        result = N - team.count(-1)
        print(result)