10451번 : 순열 사이클 - Python

문제

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

풀이

1 ~ n까지의 배열을 만들고, 입력받은 순열과 그래프를 만든다.
만든 그래프를 DFS를 이용해서 탐색한다. 연결되어 있는 그래프는 DFS한번에 1개씩 카운트 한다.

코드

from sys import stdin

input = stdin.readline

def DFS(array, v, visit):
    if visit[v]!=0: #방문 한적이 있으면 돌아간다.
        return 
    visit[v] = 1

    for i in range(len(array[v])):#가장 가까운 것 부터 계속 들어가면서 방문한다.
        if array[v][i]==1: 
            DFS(array, i,visit)



t = int(input())

for i in range(t):
    n = int(input())
    array = [i for i in range(1,n+1)] #1 ~ n까지의 수가 들어있는 배열
    array_temp = list(map(int,input().split()))
    visit = [0 for i in range(n+1)]
    count = 0

    matrix = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(n): #1~n이 가리키게 행렬을 만든다.
        matrix[array[i]][array_temp[i]] = 1

    for i in range(1,n+1):
        if visit[i] != 1:
            DFS(matrix,i,visit)
            count += 1

    print(count)

더 좋은 풀이

굳이 1~n까지의 배열을 안만들고, 반복문을 이용해 연결되어 있는 노드를 다 방문하고, count한다. 입력받은 순열의 index가 indec가 가르키는 노드가 된다.

예시) 3 2 7 8 1 4 5 6 이면 각 수의 인덱스인
3(1) 2(2) 7(3) 8(4) 1(5) 4(6) 5(7) 6(8)일때,
반복문으로 1이 가리키는 3을 방문하고 다시 3이 가리키는 7을 방문하면 된다.

더 좋은 코드

from sys import stdin

inpuit = stdin.readline

def sol(n, a):
    visited = [0] * (n + 1)
    count = 0
    for i in range(1, n + 1):
        if not visited[i]: #i를 방문 안했다면
            count += 1 #방문 횟수 
            visited[i] = 1 #i를 방문 했다고 표시
            temp = a[i] #i가 가르키는 노드를 temp에 저장
            
            #while이 다 돈다면 i에서 갈 수 있는 노드를 다 방문한다.
            while not visited[temp]: #temp를 방문 할때까지 loop
                visited[temp] = 1 #temp를 방문 했다고 표시
                temp = a[temp] #temp가 가르키는 노드를 temp에 저장
    print(count)

t = int(input())
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    sol(n, a)