[ 백준 / 파이썬 ] 10451. 순열사이클

 

🎉 문제

 

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.
N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

 

 

🎉 풀이

✅ bfs 이용

✅ 처음에는 따로 그래프 배열을 또 만들고자 했음

✅ 하지만 방문 배열만 만들어서 원래 배열의 인덱스를 이용하면 bfs를 돌릴 수 있지 않을까... 해서 한 번 해봤더니 성공

 

 

 

 

🎉 코드

from collections import deque

t = int(input()) #testcase

for _ in range(t):
  n = int(input()) #순열의 크기
  array = list(map(int, input().split()))

  queue = deque()
  visited = [False]*n #방문배열 생성
  queue.append(array[0]) #시작 정점 추가
  visited[0] = True #시작 정점 방문처리

  cnt = 0 #순열 사이클 개수

  for i in range(n): #인덱스를 이용해서 순열 사이클 확인
    if visited[i] == False: #i번째 원소를 방문하지 않았다면
      queue.append(array[i]) #정점 추가
  
    while queue: #queue의 원소가 없을 때까지 = 순열사이클이 끝날때까지
      v = queue.popleft() #정점 꺼내기
      if visited[v-1] == True: #v(정점)의 다음 원소가 이미 방문한 원소라면
        cnt += 1 #순열 사이클이므로 개수 하나 추가
      else: # v(정점)의 다음 원소가 아직 방문하지 않은 원소라면
        queue.append(array[v-1]) #큐에 추가
        visited[v-1] = True #방문처리

  print(cnt) #개수 출력