[BOJ] 9466. 텀 프로젝트

문제

텀 프로젝트 (https://www.acmicpc.net/problem/9466)

풀이

1. 초기접근

• 문제조건 해석
  • 문제를 잘 읽어보면, 주어진 데이터를 그래프로 보고, 이 중, 싸이클 인 것만 한 팀이 되는 것을 알 수 있다.
  • 즉, 주어진 학생의 수(노드) n개에서 싸이클이 아닌 학생(노드) 만 잡아내면 된다.
• 알고리즘
  • 모든 노드를 순차적으로 탐색해야 하므로, 기본적으로 DFS 다.
  • 간선을 따라 DFS를 진행하되, 다음 진행 노드가 이전에 방문된 적이 있다면 (visited), 그 노드부터 현재노드까지 싸이클 내에 있음을 알 수 있다.
  • 위 방식으로, 싸이클을 발견했다면, DFS 를 종료하고, 다시 하나씩 반대방향으로 back 하며 cycle 내에 있는 노드는 팀을 이룬다는 체크를 해준다.(team)
  • 방문한 노드는 재 방문 하지 않으므로, 시간복잡도는 O(n) 이다.
• 코드

import sys
sys.setrecursionlimit(10**8)

def dfs(idx, value, visited, total_visited):

    if idx in total_visited:
        # 현재 인덱스가 방문된 적이 있다면,
        # 이후 dfs 순회가 이미 끝난 것이므로, 더 탐색하지 않고 종료.
        return True, None

    visited.add(idx)
    total_visited.add(idx)

    if value in visited:
        # 다음 방문 인덱스(value)가 이미 방문한 적이 있다면, 사이클을 발견한 것임.
        # 다음 방문 인덱스(value)가 사이클 시작점. 
        global team
        team += 1
        return (idx == value), value

    # 사이클을 발견할 떄까지 dfs를 진행하고,
    # 찾았을 때, 사이클 시작 인덱스(start_index)와,
    # back하면서 현재 사이클 내부인지(is_cycle)이 체크.
    is_cycle, start_idx = dfs(value, students[value], visited, total_visited)
    if is_cycle == False:
        # back하면서 아직 사이클 내부라면, 현재 인덱스는 팀에 소속된 것.
        team += 1
        if idx == start_idx:
            # back하면서 현재 인덱스가 사이클 시작점이라면,
            # 이후 back하며 방문되는 인덱스는 모두 팀에 소속되지 않음.
            is_cycle = True

    return is_cycle, start_idx


tc = int(sys.stdin.readline())
for t in range(tc):
    n = int(sys.stdin.readline())
    students = list(map(int, sys.stdin.readline().split()))
    students = [x-1 for x in students]
    team = 0
    visited = set()

    for idx, value in enumerate(students):
        if idx in visited:
            continue
        dfs(idx, value, set(), visited)

    # 팀에 속하지 않은 사람 수 = 전체 인원 수 - 팀에 소속된 사람 수
    print(n - team)

2. 유의할 점

• visited 와 total_visited 이 있는데,
  '현재 탐색'에서 싸이클이 있는지 체크하기 위해 쓰는 변수가 visited 이고,
  '전체 탐색', 즉 현재노드가 한 번이라도 방문되었는지 체크하기 위함이 total_visited 이다.
• visited 가 total_visited 에 포함된다고 생각하면 된다.
• 여담으로, 초기 코드(여기에 적지는 않았지만,) 에서는 total_visited 를 두지 않고 다음과 같이 진행했다.

for idx, value in enumerate(students):
    ...
    _, _, v = dfs(idx, value, set(), visited)
    visited = visited | v
    ...

• 현재 탐색에서 얻은 방문노드들을 전체 탐색 체크리스트에 넣어주기 위한 코드였다.
• 그런데 이러면 시간이 훨씬 늘어난다. 즉 비효율적이다.
  이유인 즉슨, visited | v 코드에서 새로운 객체를 할당하게 되는데, 이 시간복잡도가 O(n) 이라고 한다.
• 하지만 위 풀이 코드처럼 할 경우, 별도로 n 번의 시간을 더 쓸 일이 없다.
• 나의 경우 저 집합 연산 | 이 저 정도의 시간을 잡아 먹는 줄 제대로 몰랐었다.
  지금이라도, 파이썬 내 각 자료형의 기본연산 시간을 제대로 알고 쓸 줄 알아야겠다.

파이썬 내장함수의 기본 시간복잡도

<https://daimhada.tistory.com/56