🥚문제

https://www.acmicpc.net/problem/9466

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

---

🥚입력/출력

---

🍳코드

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


def dfs(x):
    global ans

    visited[x] = True
    cycle.append(x)  # 지금까지의 팀 구성
    pick = arr[x]

    if visited[pick]:  # 이미 방문 했는가?
        if pick in cycle:  # cycle 내에 있는가? => cycle
            idx = cycle.index(pick)
            ans += cycle[idx:]
        return
    else:
        dfs(pick)


T = int(input().strip())
for _ in range(T):
    n = int(input().strip())
    arr = [0] + list(map(int, input().split()))
    visited = [True] + [False]*n

    # 팀을 정하는 데 성공한 학생들
    ans = []

    for i in range(1, n+1):
        if not visited[i]:
            cycle = []
            dfs(i)

    print(n - len(ans))

---

🧂아이디어

그래프, DFS

참고: https://claude-u.tistory.com/435

• 보자마자 사이클을 찾아야겠다는 생각이 떠올랐던 문제

• 다만, 방향 그래프에서 어떻게 사이클을 판별할 것인지에 대해 고민했고, 작성한 코드를 제출했을 때 시간초과/메모리초과가 번갈아 떠서 개선하는 데 시간이 걸렸다.
  • PyPy3로 제출시 메모리 초과가 발생했다.
    PyPy3가 자주 사용하는 코드를 캐싱하여 메모리를 많이 사용하는 대신 시간을 단축할 수 있다고 한다. 앞으로 알아두자.
    Python3 와 PyPy3 차이 (읽어보기)

• 방향 그래프에서의 사이클은 DFS를 통해 간단하게 판별할 수 있다.

• dfs중, 이미 방문한 정점에 다시 방문하면 사이클이 발생했다고 볼 수 있다.

• 코드의 자세한 설명은 아래와 같다.

  • ans는 팀을 정하는 데 성공한 학생들을 저장하는 리스트로, dfs 함수를 통해 업데이트 된다.

  • 아직 방문하지 않은 정점 i에서 dfs를 실행한다. 실행할 때마다, cycle이라는 리스트를 유지한다.

  • cycle은 dfs를 실행하며 방문하는 정점들을 차례로 저장하는 리스트이다.

  • dfs내부에서는

    1. 인자로 들어온 x를 방문표시하고, cycle 리스트에 x를 삽입한다. 그 뒤, x가 선택한 학생인 pick을 구한다.

    2. pick을 방문한 적이 없다면 dfs(pick)

    3. 만약pick을 이미 방문한 적이 있고, pick이 cycle 내부에 있다면 cycle 내부에 처음 등장한 pick부터 사이클을 이루고 있다는 의미이다.

       (e.g.,)
       입력이 아래와 같을 때 1에서 dfs를 시작하면 1 -> 3 -> 3으로 연결되는데 여기에서 팀이 되는 것(사이클)은 3 하나 뿐이다.

    4. cycle 내부에 처음 등장한 pick의 위치를 idx라고 할 때, 전역변수인 ans에 cycle[idx:]를 이어붙인다.

    5. 마지막으로 n에서 ans의 개수를 뺀 값이 문제에서 원하는, 팀을 이루지 못한 학생의 수이다.