728x90
https://www.acmicpc.net/problem/2668
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
import sys; input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
nums = [0]+[int(input()) for _ in range(n)]
visit = [False] * (n+1)
finish = [False] * (n+1)
result = []
def dfs(node):
global result
visit[node] = True
cycle.append(node)
next = nums[node]
if visit[next]:
if next in cycle:
ind = cycle.index(next)
for i in range(ind,len(cycle)):
num = cycle[i]
if not finish[num]:
finish[num] = True
return
dfs(nums[node])
for i in range(1, n + 1):
if not visit[i]:
cycle = []
dfs(i)
print(sum(finish))
for i in range(len(finish)):
if finish[i]:
print(i)https://sinawi.tistory.com/309
[백준] 9466 텀 프로젝트 python
import sys; input = sys.stdin.readline sys.setrecursionlimit(10**7) def dfs(node): global result visit[node] = 1 cycle.append(node) stu = st[node] if visit[stu]: if stu in cycle: result += cycle[cyc..
sinawi.tistory.com
얘와 같은 문제이다.
DFS를 연습하려고 똑같은 문제를 풀었는데 아직 사이클 구하는게 어렵다
'STUDY > Algorithm' 카테고리의 다른 글
| [백준] 2670 연속부분 최대곱 python (0) | 2021.05.30 |
|---|---|
| [백준] 1541 잃어버린 괄호 python (0) | 2021.05.26 |
| [백준] 9466 텀 프로젝트 python (0) | 2021.05.18 |
| [백준] 1992 쿼드트리 python (0) | 2021.05.18 |
| [백준] 2750 수 정렬하기 C (2) | 2021.05.18 |