[DFS/BFS/완전탐색] 10451번 - 순열 사이클(DFS/BFS)

[백준] 10451번 - 순열 사이클

풀이 시간: 20분 이내

매번 위치벡터를 이용한 DFS/BFS문제를 풀다가 오랜만에 그래프 문제를 만나 평소보다 조금 시간이 걸리긴 했지만 쉽게 풀 수 있는 문제였고 DFS, BFS 중 편한 방식으로 풀면 된다.

이 문제의 경우 메모리, 시간 측면에서 모두 DFS로 푸는 것이 더 효율적인 결과가 나왔기 때문에 DFS로 푸는 것을 추천한다.

(풀이1) DFS

1) 문제 해결 아이디어

 

2) 소스코드

t = int(input())  # 테스트 케이스 수

# DFS
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)

(풀이2) BFS

1) 문제 해결 아이디어

 

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)