[백준] 10451 - 순열 사이클 (Python)

29 Jul 2021

[백준] 10451 - 순열 사이클

https://www.acmicpc.net/problem/10451
알고리즘:
- 그래프 이론
- 그래프 탐색
- 순열 사이클 분할

풀이1 - BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
T=int(input())

def bfs(V):
    queue = [V]
    visited[V] = 1  #방문한 곳 1로 표시
    while queue:
        V = queue[0]
        queue.pop(0)
        next = arr[V]
        if visited[next] == 0: #아직 방문하지 않은 곳인 경우
            visited[next] = 1
            queue.append(next)
    return 1

for i in range(T):
    answer = 0
    N = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [0] * (N + 1)

    for i in range(1, N+1):
        if visited[i] == 0:
            answer += bfs(i)
    print(answer) #순열 사이클의 개수

처음에 BFS를 이용하여 문제를 풀었지만, 이 문제는 DFS를 이용하여 푸는 것이 좀더 적합하다고 생각하여 DFS를 이용하여 다시 풀어보았다.

풀이2 - DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
sys.setrecursionlimit(10**7)

T=int(input())

def dfs(V):
    visited[V]=1  #방문한 곳 1로 표시
    next=arr[V]
    if visited[next]==0: #아직 방문하지 않은 곳인 경우
        dfs(next)

for i in range(T):
    answer = 0
    N = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [0] * (N + 1)

    for i in range(1, N+1):
        if visited[i]==0:
            dfs(i)
            answer+=1
    print(answer) #순열 사이클의 개수

algorithms