Problem Solving
[BOJ] 2668번 숫자고르기
주씨.
2022. 1. 7. 18:29
728x90
https://www.acmicpc.net/problem/2668
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
# 1
N = int(input())
graph = [-1]
for i in range(1, N+1):
graph.append(int(input()))
res = []
def dfs(v):
visited[v] = True
ret = graph[v]
if not visited[graph[v]]:
ret = dfs(graph[v])
return ret
for i in range(1, N+1):
visited = [False] * (N+1)
ret = dfs(i)
if ret == i:
res.append(i)
print(len(res))
print(*res, sep='\n')
# 2
N = int(input())
graph = [-1]
for i in range(1, N+1):
graph.append(int(input()))
res = []
def dfs(v, start):
visited[v] = True
if not visited[graph[v]]:
dfs(graph[v], start)
if graph[v] == start:
res.append(start)
for i in range(1, N+1):
visited = [False] * (N+1)
dfs(i, i)
print(len(res))
print(*res, sep='\n')
여전히 약한 dfs...
다음 노드를 방문하지 않았을 때 다음 노드에 대하여 dfs 수행.
방문했을 경우 조건 확인 (싸이클 형성 여부).