[BOJ] 10451. 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

풀이

• DFS문제.

• 처음 시작노드 -> 방문안한노드를 방문 -> 방문한 노드를 마주치면 while문 밖으로

• 처음 시작노드 = 최종 도착노드일 경우(cycle) count 변수 +1해줌.

  def solution():
      n = int(input())
      lst = [0] + list(map(int, input().split()))
      cnt = 0
      visited = [False] * (n+1)
      
      for i in range(1, n+1):
          # 이미 방문한 노드
          if visited[i] == True: continue
  
          # 방문 정보 업데이트
          visited[i] = True
          
          # 배열 복사
          check_visited = visited[::]
          
          # 최초 시작노드, 도착노드 지정
          start_point =  i
          end_point = lst[i] 
          
          # 방문하지 않은 노드인지 확인
          while check_visited[end_point] == False:
              check_visited[end_point] = True
              # 도착지점 update
              end_point = lst[end_point]
          
          # 노드를 재방문할경우 while문 탈출
          # visited 배열 업데이트
          visited = check_visited
          
          # 마지막 방문노드와 첫번째 시작 노드와 같을 경우(cycle)에만 +1을 더해줌
          cnt = cnt + 1 if end_point == start_point else cnt
      return cnt
  
  for _ in range(M):
      print(solution())