백준 실버3 DFS 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 26분

import sys
sys.setrecursionlimit(2000)

def dfs(k,nums,visitied,ans):
    if not visitied[k]:
        visitied[k]=True
        dfs(nums[k]-1,nums,visitied,ans)

    return 1


T = int(input())

for i in range(T):

    N = int(input())
    nums = list(map(int,input().split()))
    visitied = [False for j in range(N)]
    ans = 0
    
    for k in range(len(nums)):
        if not visitied[k]:
            ans += 1
        dfs(k,nums,visitied,ans)
    print(ans)

1부터 N까지의 정수 순열이 주어지고 인덱스-값 끼리 연결되는 것을 사이클이라고 정의했을 때, 입력되는 순열별 사이클의 갯수를 구하는 문제입니다.🐇🐇🐇

인덱스를 돌며 인덱스에 해당하는 값을 다시 해당하는 인덱스로 탐색하는 문제이므로 DFS(재귀함수)로 구현하여 해결할 수 있었습니다.

[다른 사람의 풀이1]

def dfs(v):
  visited[v] = True  # 현재노드 방문처리
  nv = graph[v]      # 인접 노드
  # 아직 방문하지 않은 노드라면 dfs 호출
  if not visited[nv]:
    dfs(nv)
  
for _ in range(t):
  n = int(input())  # 순열 크기
  graph = list(map(int, input().split()))  # 순열(n개)
  graph.insert(0, 0)  
  visited = [False] * (n + 1)  # 1 ~ n 사용
  cycle = 0  # 순열 사이클 개수

  for i in range(1, n + 1):
    # 방문하지 않은 노드라면
    if not visited[i]:
      dfs(i)      # i노드에서 dfs 호출
      cycle += 1  # 사이클 개수 1증가
  print(cycle)

'나의 풀이'와 같이 DFS, 재귀함수를 활용한 풀이입니다.🐤🐤🐤

[다른 사람의 풀이2]

from collections import deque
t = int(input())  # 테스트 케이스 수

# BFS
def bfs(v):
  queue = deque()
  # 시작 노드 삽입, 방문 처리
  queue.append(v)
  visited[v] = True

  while queue:
    v = queue.popleft()
    nv = graph[v]
    # 방문하지 않는 노드라면
    if not visited[nv]:
      queue.append(nv)
      visited[nv] = True
  
for _ in range(t):
  n = int(input())  # 순열 크기
  graph = list(map(int, input().split()))  # 순열(n개)
  graph.insert(0, 0)  
  visited = [False] * (n + 1)  # 1 ~ n 사용
  cycle = 0  # 순열 사이클 개수

  for i in range(1, n + 1):
    # 방문하지 않은 노드라면
    if not visited[i]:
      bfs(i)      # i노드에서 bfs 호출
      cycle += 1  # 사이클 개수 1증가
  print(cycle)

같은 구조이되 DFS대신 Queue를 활용한 BFS로 구현한 풀이입니다.

감사합니다.