[백준-2668] 숫자고르기 - Python

 

 

 

문제 소개

 

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

 

 

 

사용한 알고리즘

 

 

DFS (루트 저장)

DFS 중에서 진행된 루트를 저장하는 DFS를 하면된다. 
비슷한 문제로는 https://dizzy-theme.tistory.com/53가 있다.

 

 

 

 

구상

 

첫번째줄에서 뽑은 숫자와 그에 연결된 두번째 수의 배열이 같으려면 (순서는 상관없이)
당연한 소리지만 두 집합의 크기가 같아야 한다.
따라서 크기가 같은 집합에서 서로 화살표가 빠지는 원소 없이 그어져 있는 경우이고
이 경우 순환관계가 성립된다.
따라서 집합의 순환관계가 성립하는 가장큰 집합을 고르면되기 때문에 원소 하나에서 시작해서 순환관계가 나오면 추가 시키고 안나오면 빼는 형식으로 진행하면 된다.

이 과정에서 내가 이전에 파악한 순환관계가 성립하는 원소를 [ 2,5,7 ] 이라고하면 이후 탐색에서 [2,5,7]은 빼고 탐색해야 하기 때문에 DFS중에서 여태까지 탐색한 루트를 list 로 저장하는 DFS를 해야한다.
(참고로 그렇게 구현하려면 탐색한 루트도 DFS함수에 넣어주는 DFS함수를 만들어야 한다)

 

 

 

Code 

 

#############################################################################
#
#############################################################################

import sys
import collections



sys.stdin = open("input.txt", "r")

input=sys.stdin.readline

N = int(input())

graph = collections.defaultdict(list)
for k in range(N):
    graph[k+1].append(int(input()))


maxlist=[]
def DFS(startNode ,list0 ):
    global maxlist
    if startNode in maxlist:
        return
    list0.append(startNode)
    if len(list0) > 0 and list0[0] == graph[startNode][0]:
        #print('return' , list0)
        return maxlist.extend(list0)
    elif graph[startNode][0] not in list0:
        #print('DFS',startNode,list0)
        DFS(graph[startNode][0],list0)

for k in graph.keys():
    DFS(k,[])

maxlist.sort()
print(len(maxlist))

[print(maxlist[x]) for x in range(len(maxlist))]

 

 

 

마무리

 

추가 반례

7
2
6
5
4
3
2
7

답 6

 

6
2
3
1
5
6
4

답 6

 

 

 

※ end