백준 알고리즘 - 텀 프로젝트 (9466) [Python]

 

 

 문제

 

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

 

 

 

 

 

 문제 상황

 

- 주어진 리스트의 부분 사이클을 구해 팀을 구성하고, 팀이 없는 학생 수를 구한다.

 

 

 

 

 

 

 해결 전략

 

- 재귀보다는 반복을 통해 구한다. 내 방법으로는 조건을 통해 사이클이 되는지 안되는지를 확인하는 알고리즘을 사용하여 만약 부분적으로 사이클을 이룬다면 그 부분만 사이클이 된다고 표시하고 넘어가는 방식을 택한 후 사이클에 포함 안되는 요소의 개수를 찾았다. 하지만 이 방식으로는 속도 이슈가 발생하였다.

 

- 다른 블로그를 참고하여 얻은 방법은 우선 사이클을 계속 찾아 들어간 후 마지막을 만났을 때, 다시 그 부분부터 역순으로 돌아가며 사이클을 이루는 부분을 찾는다. 즉, 사이클을 이루기 때문에 사이클의 어느 시점에서 시작하여도 한바퀴를 돌 수 있다는 특징을 이용하였다.

 

 

 

 

 

 

 코드

 

# 통과 코드
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
    n = int(input()) # 학생들의 수
    n_list = [0] + list(map(int, input().split()))
    in_group = [0]*(n+1)
    group = 1
    for i in range(1, n+1):
        if in_group[i] == 0:
            while in_group[i] == 0 : # 사이클을 만날 때 까지 반복
                in_group[i] = group # 그룹 번호를 부여
                i = n_list[i]
            while in_group[i] == group : # 완성된 사이클을 역순으로 반복
                in_group[i] = -1 # 사이클을 이루면 -1을 할당
                i = n_list[i]
            group += 1
    cnt = 0
    for i in range(1, n+1):
        if in_group[i] > 0 : cnt+=1
    print(cnt)
 
# 속도 이슈 코드
from sys import stdin
input = stdin.readline
def dfs(start, n_list):
    temp = [start]
    while True:
        check_node = temp[-1]
        target_node = n_list[check_node]
        if target_node == start: # 연결고리가 돌아서 start와 같다면
            for i in range(len(temp)):
                in_group[temp[i]] = True
            break
        elif target_node not in temp:
            temp.append(target_node)
        elif target_node in temp:
            break
for _ in range(int(input())):
    n = int(input()) # 학생들의 수
    n_list = [0] + list(map(int, input().split()))
    in_group = [True] + [False]*(n)
    for i in range(1, n+1):
        if in_group[i] is False:
            dfs(i,n_list)
    print(in_group.count(False))

 

 

 

 

 

 

 

 

 해설

 

- 속도 이슈 발생은 조건을 확인한 후, 조건에 만족하면 그때 in_group 체크 리스트를 갱신하는 방향으로 하였지만 여기에서 속도 이슈가 발생하는 듯 하다.

 

- 더 좋은 방법은 사이클의 특성을 이용해 갱신할 때 일일이 목록을 저장해두는 것이 아니라 마지막 시점부터 다시 돌면서 사이클 여부를 갱신하는 것이다.

 

- 속도 이슈코드는 O(N^3) 이고 통과 코드는 while구문이 병렬로 되어있어 O(N^2)로 해결 가능하다. 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 체크를 할 때, 내용을 저장해두고 갱신하는 방법도 있지만 전체 사이클에서 일부분을 찾는 문제의 경우 마킹을 해두고 그 마킹을 검색하며 조건을 만드는 것도 방법이다.