[백준] 10451번

그녕·2023년 3월 7일
0

알고리즘 문제 풀이

목록 보기
10/29

백준 10451번

DFS

💗내 풀이💗

딱 보자 마자 DFS,BFS 문제구나 생각이 들긴 했는데 아직 잘 모르겠어서 못 풀었다.
차근 차근 풀이를 살펴보겠다.

sys.setrecursionlimit(10**7)

최대 재귀를 늘려줘야 런타임 에러를 피할수 있다고 한다.
DFS는 재귀또는 스택을 이용해서 푸는 문제가 많다.
dfs함수를 정의해서 dfs함수가 들어가면 방문했다는 거니깐 visited 리스트에 값을 1로 바꿔준다. 그리고 그 다음 값을 넣어줘야하므로 next를 선언해주었다. 그리고 다음 값에 방문을 안한거라면(visited[next]==0)이라면 다시 그 함수를 적용한다. 만약 방문을 했다면 함수가 끝나서 나오게 된다. 그렇다면 원래 for문에서 ans가 하나 증가하게 되어서 순환개수가 하나 증가하게 되는 것이다.

data = [0]+list(map(int,input().split()))

왜 이렇게 써야하지?
->그냥 인덱스 1부터 써주려고 하는거였다

💗내 코드💗

import sys
sys.setrecursionlimit(10**7)
T= int(input())

def dfs(v):
    visited[v]=1
    next= data[v]
    if visited[next]==0:
        dfs(next)
    

for _ in range(T):
    N= int(input())
    data = [0]+list(map(int,input().split()))
    visited= [0]*(N+1)
    ans=0
    for i in range(1,N+1):
        if visited[i]==0:
            dfs(i)
            ans+=1
    print(ans)

0개의 댓글