[백준] 10451. 순열사이클
https://www.acmicpc.net/problem/10451
문제
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.
순열을 배열을 이용해 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.
Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.
N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
BFS
import sys
from collections import deque
input = sys.stdin.readline
testcase = int(input())
for _ in range(testcase):
n = int(input())
cycle_input = list(map(int, input().split()))
cycle = dict()
for idx, i in enumerate(cycle_input):
cycle[idx + 1] = i
visited = [0] * (n + 1)
cnt = 1
for i in cycle:
if visited[i] == 0:
q = deque([i])
visited[i] = cnt
while q:
cur = q.popleft()
if visited[cycle[cur]] != 0: continue
visited[cycle[cur]] = cnt
q.append(cycle[cur])
cnt += 1
print(cnt-1)
DFS
import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline
testcase = int(input())
def dfs(x):
visited[x] = True
cycle = cycle_input[x]
if not visited[cycle]:
dfs(cycle)
for _ in range(testcase):
n = int(input())
cycle_input = [0] + list(map(int, input().split()))
visited = [True] + [False] * n
result = 0
for i in range(1, n + 1):
if not visited[i]:
dfs(i)
result += 1
print(result)
Author And Source
이 문제에 관하여([백준] 10451. 순열사이클), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nayoon-kim/백준-10451.-순열사이클저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)