카테고리 없음

백준 파이썬 2688 숫자고르기

작지 2022. 2. 28. 16:00

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

 

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절

www.acmicpc.net

 

 

dfs 문제인데 저장을 어떻게 하지? 라는 생각에 엄청 시간이 걸린거같다.

 

def dfs(x,idx):
    visited[x] = 1

    for i in matrix[x]:
        if visited[i] == 0:
            dfs(i,idx)
        elif visited[i] == 1 and i == idx:
            result.append(i)

n = int(input())

s1 = [i+1 for i in range(n)]
s2 = [int(input()) for i in range(n)]

matrix = [[] for i in range(n)]

for i in range(n):
    matrix[s1[i]-1].append(s2[i]-1)

result = []

for i in range(n):
    visited = [0] * n
    dfs(i,i)

print(len(result))
for i in result:
    print(i+1)

쓸데없이 어렵네