Algorithm/DFS&BFS

9466๋ฒˆ/DFS ํ…€ ํ”„๋กœ์ ํŠธ/ํŒŒ์ด์ฌ

์ •ํ˜ธ๋‚˜ 2024. 9. 29. 15:17

๐Ÿ“• ๋ฌธ์ œ

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

 

๐Ÿ“—์‹คํ–‰๊ฒฐ๊ณผ

 

 

๐Ÿ“„ ๋‚ด๊ฐ€ ์ƒ๊ฐํ•œ ํ’€์ด

 

 

์‚ฌ์ดํด์ด ๋งŒ๋“ค์–ด์ง€๋Š” ํ•™์ƒ์ด ํŒ€์ด ๋งŒ๋“ค์–ด์ง.

 

 

๐Ÿ’ป ๋‹ต์•ˆ

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(x,result):
    visited[x] = True
    # ์‚ฌ์ดํด์„ ์ด๋ฃจ๋Š” ํŒ€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด
    cycle.append(x)
    number = arr[x]

    # ๋ฐฉ๋ฌธ๊ฐ€๋Šฅํ•œ ๊ณณ์ด ๋๋‚ฌ๋Š”์ง€
    if visited[number]:
        # ์‚ฌ์ดํด ๊ฐ€๋Šฅ ์—ฌ๋ถ€
        if number in cycle:
            # ์‚ฌ์ดํด ๋˜๋Š” ๊ตฌ๊ฐ„ ๋ถ€ํ„ฐ๋งŒ ํŒ€ ์ด๋ฃธ
            result += cycle[cycle.index(number):]
        return
    else:
        dfs(number,result)



# ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์ธ int(input())๋งŒํผ ์ˆ˜ํ–‰ 
for _ in range(int(input())):
    # n : ํ•™์ƒ ์ˆ˜
    n = int(input())
    # ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ
    arr = [0] +list(map(int,input().split()))
    visited = [False for _ in range(n+1)]
    result =[]
    
    for i in range(1,n+1):
        # ๋ฐฉ๋ฌธ ์•ˆํ•œ ๊ณณ์ด๋ฉด
        if not visited[i]:
            # cycleํ–‰๋ ฌ ์ƒ์„ฑํ•ด์„œ
            cycle = []
            # dfsํ•จ์ˆ˜ ๋Œ๋ฆผ
            dfs(i,result)

    # ํŒ€์— ์—†๋Š” ์‚ฌ๋žŒ์ˆ˜
    print(n-len(result))

 

โ˜บ๏ธ ๋А๋‚€์ 

DFS/BFS ์–ด๋ ค์›€

์ฐธ๊ณ ์ž๋ฃŒ ๋ด์•ผ ๊ตฌํ˜„๊ฐ€๋Šฅ

 

 

๐Ÿ˜‰ ์ฐธ๊ณ 

https://oh2279.tistory.com/138

 

[๋ฐฑ์ค€/ํŒŒ์ด์ฌ] 9466๋ฒˆ ํ…€ ํ”„๋กœ์ ํŠธ

https://www.acmicpc.net/problem/9466 9466๋ฒˆ: ํ…€ ํ”„๋กœ์ ํŠธ ์ด๋ฒˆ ๊ฐ€์„ํ•™๊ธฐ์— '๋ฌธ์ œ ํ•ด๊ฒฐ' ๊ฐ•์˜๋ฅผ ์‹ ์ฒญํ•œ ํ•™์ƒ๋“ค์€ ํ…€ ํ”„๋กœ์ ํŠธ๋ฅผ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•œ๋‹ค. ํ”„๋กœ์ ํŠธ ํŒ€์› ์ˆ˜์—๋Š” ์ œํ•œ์ด ์—†๋‹ค. ์‹ฌ์ง€์–ด ๋ชจ๋“  ํ•™์ƒ๋“ค์ด

oh2279.tistory.com

 

 

https://www.youtube.com/watch?v=yPuow6aACvE