백준/ Gold 4 문제 , 백준 파이썬 2668 , 숫자고르기 [DFS]

백준/ Gold 4 문제 , 백준 파이썬 2668 , 숫자고르기 [DFS]

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
반례들이 다 한번에 통과하지 않아서 코드를 계속해서 수정해가며 풀었다.

 

문제 출처

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

2668번: 숫자고르기

 

반례

 

6
2
3
1
5
6
4

 

정답

1
2
3
4
5
6

 

 

10
2
4
1
7
7
4
4
8
2
1

 

정답

 

3

4

7

8

 

9
5
6
2
8
3
4
2
7
6

 

정답

 

5

2

4

6

7

8

 

 

풀이

 

1. DFS 

 

우선 호출된 숫자의 아래 숫자로 탐색을 시작한다.

 

방문하지 않았던 곳이면 dq에 넣어주고 방문 표시를 하며, store에 저장해 나간다.

 

 

위의 elif X==x 는 숫자들을 탐색해 돌아 처음 호출된 자기 자신으로 돌아오는 경우를 식별해준다.

 

이 경우 store에 담긴 숫자들을 다 리턴시켜준다.

 

 

아래 elif tmp==X 는 [5,5] 와 같이 자기자신이랑 연결되어있는 집합을 구별해준다.

 

이런 숫자들은 무조건 뽑아줘야 하므로 바로 해당 숫자만 return 시켜준다.

 

 

이후 return 되지 않고 while문을 그냥 빠져 나와버린다면 store에 담긴 숫자들은 return 되기에 적절치 않은 숫자들이므로

 

방문 표시를 다시 없애주고 빈 리스트만 return 한다.

 

 

2. 입력 받기 및 DFS 호출&처리

 

visited를 선언해 방문 유무를 확인해주고 제대로 방문 되지않은 숫자들만 dfs 를 호출해준다.

 

앞에서 탐색했던 숫자들이더라도 의미없는 방문이였다면 재 탐색한다.

 

이후 tmp 변수에 return 값을 넣어 result 리스트에 넣어준뒤 

 

sort로 정렬하여 출력 값에 맞게 출력한다.

 

 

 

 

정답

 

from collections import deque
import sys
input=sys.stdin.readline

def dfs(x):
    dq=deque()
    dq.append(x)
    store=[]
    while dq:
        X=dq.popleft()
        tmp=nums[X-1][1]
        if visited[tmp]==0:
            dq.append(tmp)
            visited[tmp]=1
            store.append(tmp)
        elif X==x:
            return store
        elif tmp==X:
            return [X]
    for i in store:
        visited[i]=0
    return []

N=int(input())
nums=[[i,int(input())] for i in range(1,N+1)]
visited=[0 for _ in range(N+1)]
result=[]
for j in range(1,N+1):
    if visited[j]==0:
        tmp=dfs(j)
        for k in tmp:
            result.append(k)
result.sort()
print(len(result))
for i in result:
    print(i)