๐ ๋ฌธ์
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
'Algorithm > DFS&BFS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด์ฝํ ] DFS/BFS/ ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ (0) | 2024.10.30 |
---|---|
[์ด์ฝํ ]DFS/BFS/ ์๋ฃ์ ์ผ๋ ค๋จน๊ธฐ (1) | 2024.10.22 |
1240๋ฒ/DFS ๋ ธ๋์ฌ์ด๊ฑฐ๋ฆฌ/ํ์ด์ฌ (2) | 2024.09.28 |
10026๋ฒ/ BFS ์ ๋ก์์ฝ/ ํ์ด์ฌ (1) | 2024.09.13 |
1260๋ฒ / DFS์ BFS / ํ์ด์ฌ (1) | 2024.09.08 |