[Gold V] 숫자고르기 - 2668 (집합, DFS)

[Gold V] 숫자고르기 - 2668

문제 링크

성능 요약

메모리: 32452 KB, 시간: 96 ms

분류

깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

1~2시간 정도 고민하다 결국 풀지 못하고 풀이를 참조했다. 

처음엔 그냥 연결된 그래프를 구하면 될 줄 알았는데, 직접 출력해보니 완전 잘못 이해한 것이었고, 고민끝에 사이클이 존재하면 집합에 포함된다는 것을 눈치챘다. 

예제 테스트 케이스까지 맞췄지만, 아이디어가 잘 떠오르지 않아 뭔가 생각나는대로 하다보니 코드가 지저분했고 원인을 쉽게 찾을 수 없었다.

결국 풀이를 참조했고, 모든 사이클이 있는 곳을 찾아 빈 리스트 딕셔너리와 집합을 이용하여 아주 간단하게 구현이 가능했다.

 

-풀이 순서

1.딕셔너리 key값에는 두 번째 줄에 오는 값을 넣고, value 값에는 첫 번째 줄의 값을 넣는다.

2. 방문하지 않은 곳이라면 그 장소와 집합 함수를 dfs 파라미터에 넣어 탐색한다.

3. 집합 함수에 방문하지 않은 장소를 넣고(add) 방문 체크를 한다.

4. 딕셔너리 key 값을 기준으로 value값을 보며 방문하지 않았으면 dfs를 계속 돌려주고, 방문했다면 사이클이 있다는 뜻으로 정답을 저장할 리스트(answer)에 추가(extend)해준다.

5.정답 리스트의 길이(len(answer))와 정렬한 값을 출력한다.

 

부족했던 점 : 사이클이라는 키워드를 알아냈지만, 구체적인 방안을 제시하지 못했음. 정확한 방법은 모든 사이클을 탐색해야했음.

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x, visit):
    visit.add(x)
    visited[x] = 1
    for i in dic[x]:
        if i not in visit:
            dfs(i, visit.copy())
        else:
            answer.extend(list(visit))
            return

n = int(input())
dic = defaultdict(list)
for i in range(1, n+1):
    dic[int(input())].append(i)

visited = [0] * (n+1)
answer = []
for i in range(1, n+1):
    if not visited[i]:
        dfs(i, set([]))

answer.sort()
print(len(answer))
for i in answer:
    print(i)

#참고 풀이 출처 : https://my-coding-notes.tistory.com/519