BOJ 10451

Input

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

T = int(input())

for _ in range(T):
  N = int(input())
  P = list(map(int, input().split()))
  P.insert(0, None)

BFS

• 각 index에 들어있는 value를 다시 index로 설정해서 visited[index] == False 일 때까지 이를 반복한다.

• 결국 queue가 빌 때까지 이를 반복한다고 생각하면, BFS로 해결할 수 있다.

• 해당 사이클이 모두 visited 라면, 1을 반환하여 count++ 한다.

  def bfs(idx):
    queue = [idx]
  
    while queue:
      now = queue.pop(0)
      if not visited[now]:
        visited[now] = True
        val = P[now]
        queue.append(val)
    
    return 1

• 이후 다음 사이클로 넘어가야 하는데, 이는 결국 배열의 모든 요소를 돌아 사이클을 확인해봐야 하는 것과 같다. 따라서 visited 를 활용해 이미 방문한 요소 외의 것들의 사이클을 확인한다.

  visited = [False for _ in range(N+1)]
  count = 0
    
  # idx -> val -> idx 계속 따라가기
  for idx in range(1, N+1):
    if not visited[idx]:
      count += bfs(idx)

Better Solution

### 런타임 에러 바로잡기!!! `sys.setrecursionlimit(2000)`
import sys
sys.setrecursionlimit(2000) #최대 재귀를 늘려줘야 런타임 에러를 피할 수 있다

def dfs(x): #DFS 함수 정의
    visited[x] = True #방문 체크
    number = numbers[x] #다음 방문 장소
    if not visited[number]: #방문하지 않았다면
        dfs(number) #재귀

# 변수 할당 없이 바로 for문 돌리기! (재사용 안 함)
for _ in range(int(input())):
    N = int(input())
    
    # index를 임의로 설정하기 위해서,
    # - 따로 생성한 뒤 append이든
    # - 초기화 후 insert 하지 않고!
    ### `[0] +` 로 생성할 때 바로 임의로 초기화 값 전달!
    numbers = [0] + list(map(int, input().split()))
    
    # for 문 대신, 동일한 값으로 초기화 시 `*` 사용하기!
    visited = [True] + [False] * N #방문여부확인용
    result = 0
    
    for i in range(1, N+1):
        if not visited[i]: #방문하지 않았다면
          	# dfs의 역할:
            # 1. visited 체크
            # 2. 재귀호출로 사이클 체크 (visited)
            dfs(i) #DFS실행
            result += 1 #결과값 += 1
    print(result)

Output

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

print(count)