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

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

📌 문제 탐색하기

목표

• 순열을 그래프로 만들어서 얼마나 많은 사이클이 나오는지 출력하기

입력값

• 첫째 줄에 테스트 케이스 개수인 정수 t를 입력한다.
• 각 테스트 케이스의 첫째 줄에는 순열의 크기 N이 주어진다. (2 ≤ N ≤ 1,000)
• 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
• ex)
• 2 8 3 2 7 8 1 4 5 6 10 2 1 3 4 5 6 7 9 10 8

출력값

• 각 테스트 케이스마다 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
• ex)
• 3 7

📌 코드 설계하기

해결 아이디어

• 순열이 이어진 그림을 보고 연결리스트를 먼저 떠올렸다.
• 배열의 인덱스를 1부터 시작할 수 있게끔 0번 인덱스에 0값을 미리 저장해서 시작하고 1번 인덱스부터 입력된 배열을 순환하자.
• ListNode class를 만들어서 한 사이클이 만들어질 때까지 linked list를 만들어주자.
• 한 사이클이 돌면 Number를 1 더해주고 길이까지 저장하기 위해서 cnt로 1 더해준다.
• 이미 다른 순열 사이클에 포함되어있다를 표시하기 위해서 used 배열을 하나 더 둬서 linked list에 추가될 때마다 used 배열의 해당 인덱스 value를 1로 업데이트한다.
• 마지막에 number를 출력하면 총 순열 그래프의 개수가 나올 것이다!

📌 정답 코드

import sys

t = int(sys.stdin.readline())

class ListNode:
    def __init__(self, value, next = None):
        self.value = value
        self.next = next

for i in range(t):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    used = [0]* (len(arr)+1)
    arr.insert(0, 0)
    number = 0
    for j in range(1, len(arr)):
        if used[j] == 0:
            head = ListNode(j)
            currentNode = head
            used[j] = 1
            currentNode.next = ListNode(arr[j])
            currentNode = currentNode.next
            used[arr[j]] = 1
            j = arr[j]
            cnt = 1
            while(currentNode.value != head.value):
                currentNode.next = ListNode(arr[j])
                currentNode = currentNode.next
                used[arr[j]] = 1
                j = arr[j]
                cnt += 1
            number += 1
    print(number)

• try except를 써서 무조건 처음에는 next node를 추가하도록 했었어야 했나 생각이 든다.

시간 복잡도 구해보기

• 입력
  • 배열을 입력하는 과정이므로 O(N)
  • 처음에 insert(0, 0)은 시간 복잡도에는 영향을 미치지 않는다.
• for문
  • len(arr)만큼 for문을 돈다. → O(N)
  • used[j] == 0인 경우에만 처리한다. 이미 사용된 노드는 다시 처리되지 않는다. 따라서 각 노드는 최대 한 번만 while문에 들어간다.

최종 시간 복잡도: O(N)

📌 다른 풀이

import sys
sys.setrecursionlimit(10000)

T = int(sys.stdin.readline())

def dfs(x):
    used[x] = True
    next_node = arr[x]
    if not used[next_node]:
        dfs(next_node)

for i in range(T):
    n = int(sys.stdin.readline())
    input_arr = list(map(int, sys.stdin.readline().split()))
    arr = [0] + input_arr
    used = [False] * (n+1)
    count = 0

    for j in range(1, n+1):
        if not used[j]:
            dfs(j)
            count += 1
    print(count)

• 다른 풀이를 보는데 거의다 dfs로 풀어져있었다. 헉.. dfs 개념만 알고 직접 적용해본적은 없는데 dfs로 푸는 방식을 알아보았다.
• dfs 함수를 통해서 하나의 사이클을 만들고 count를 1 추가하는 것이다.
• 아직 방문하지 않은 노드부터 출발해서 다음 노드를 따라가며 끝까지 탐색한다. 이렇게 한 사이클이 완성되는 것이다.

DFS

• 그래프의 연결 요소를 순회하거나 사이클 또는 경로를 추적할 때 가장 많이 쓰이는 알고리즘이다.
• 모든 정점을 한 번씩 방문하면서 방문한 곳은 다시 가지 않고 끝까지 가는 경로를 따라가며 하나의 사이클을 찾고 싶다. → DFS의 정의이다.