백준 - 순열 사이클 (DFS)

백준 순열 사이클

소스코드

DFS 첫 번째 문제

https://ansanghyun20.github.io/algorithm/2021/12/03/DFS-BFS.html
stdin을 사용하지 않으면 시간초과
DFS로 모든 경우의 수를 구하는 방법
del graph[n]으로 방문했던 키 삭제

import sys
def DFS(graph, lst_root, a):
    cnt = 0
    for i in range(a):
        visited = []
        stack = [lst_root[i]]
        while stack:        
            n = stack.pop()
            if n not in visited:       
                if n in graph:
                    visited.append(n)
                    stack += set(graph[n]) - set(visited)
                    del graph[n]
        if visited:
            cnt +=1
    return cnt

graph = {}

n = int(input())

for i in range(0,n):
    a = int(sys.stdin.readline())
    ran = list(range(1,a+1))
    lst = list(map(int,sys.stdin.readline().split()))

    for i in range(0,a):
            graph[ran[i]] = [lst[i]]
            
    print(DFS(graph,lst,a))

결과

입력

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

DFS 응용 문제

1회전 마다 해당하는 순회를 모두 1로 만들어주는 알고리즘

visited를 [0, 0, 0 …] 갯수만큼 지정
visited가 0일 때 카운트 증가
stack 0, 1, 2 … 순으로 증가
num은 stack에서 pop
n은 lst(테스트 케이스에서 주어진 2번째 list)[num] 에 해당하는 값
visited[n]이 0 일 때 방문하지 않아도 되므로 1로
stack에 n 추가

def DFS(lst, a):
    cnt = 0
    visited = [0] * a
    for i in range(a):        
        stack = [i]
        if visited[i] == 0:
            cnt += 1
            visited[i]=1
        while stack:
            num = stack.pop()
            n = lst[num]-1
            if visited[n]==0:
                visited[n]=1
                stack.append(n)
    return cnt

n = int(input())
for i in range(0,n):
    a = int(input())
    ran = list(range(1,a+1))
    lst = list(map(int,input().split()))
    print(DFS(lst, a))
    

결과

12/7 DFS 재귀 알고리즘 풀이

DFS는 Stack 보다 재귀 방식에서 수행속도가 우월하다.

def dfs(graph, v, visited) :
    # 시작점은 방문한것으로 처리
    visited[v] = True
    for i in graph[v] :
        if not visited[i] :
            dfs(graph, i, visited)

n = int(input())

# 입력 값 처리
for i in range(0,n):
    a = int(input())
    ran = list(range(1,a+1))
    lst = list(map(int,input().split()))
    li = [[]]
    for i in range(len(lst)):
        li.append([lst[i]])

    visited = [False]* len(li)
    cnt = 0
    for i in range(1, len(li)):
        if visited[i]==False:    
            dfs(li, i, visited)
            cnt += 1
    print(cnt)