[백준🥇5] #2668 숫자고르기 (Python)

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

2668번: 숫자고르기

 

문제

세로 두 줄, 가로로 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

7
3
1
1
5
5
4
6

예제 출력 1

3
1
3
5

 

✔️ Code 1

n = int(input())
graph = [[] for _ in range(n+1)]
result = set()
# dict = {}
# tuple = ()

for i in range(1, n+1):
    graph[int(input())].append(i)

for i in range(1, n+1):
    visited = [0] * (n+1)
    stack = [i]
    visited[i] = 1

    while stack:
        v = stack.pop()
        for j in graph[v]:
            if not visited[j]:
                stack.append(j)
                visited[j] = 1
            elif visited[j] and i == j: # 이미 방문했고, i == j => 사이클 형성
                result.add(j)

result = list(result)
result.sort()

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

 

✔️ Code 2

n = int(input())

graph = [[] for _ in range(n+1)]
result = []

def dfs(v, i):
    visited[v] = 1

    for k in graph[v]:
        if not visited[k]:
            dfs(k, i)
        
        elif visited[k] and k == i:
            result.append(k)


for i in range(1, n+1):
    graph[int(input())].append(i)

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

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

 

✏️ Comment

어떻게 풀어야할지 모르겠어서 한 3일간 미뤘던 문제인데 결국 구글링의 도움을 받았다..
첫 번째는 따로 dfs 함수 생성 없이 stack에서 pop하면서 비교하는 방법이고 두 번째는 dfs 재귀를 이용한 풀이이다.
찾아보니 "사이클" 을 계산해야 하는 문제라고 한다. 
아래의 코드로 설명을 해보겠다.

예제를 살펴보겠다.
1 2 3 4 5 6 7
3 1 1 5 5 4 6

graph[1] = [2, 3]
graph[2] = []
graph[3] = [1]
graph[4] = [6]
graph[5] = [4, 5]
graph[6] = [7]
graph[7] = []

이런식으로 배열 위쪽의 수를 정점, 아래쪽의 수를 간선 방향이라고 생각하고 그래프에 넣어준다.
그리고나서 1부터 n까지 순서대로 for문을 돌면서 dfs 함수를 실행한다.
이때, dfs의 매개변수로 (i, i) 를 넣어주는데, 첫 번째는 dfs의 시작 부분인 i이고, 두 번째는 재귀를 계속 들어가서 찾은 값이 같은지 비교하기 위한 i이다. 
만약 이미 방문한 노드이면서 k == i 라면 result에 넣어준다.

1부터 n+1 까지 dfs를 실행할 때마다 dfs 재귀 상황(?)과 각각의 result를 보면 다음과 같다.
i=1, dfs(1) -> dfs(2) -> dfs(3) 
result = [1]

i=2, dfs(2) 
result = [1]

i=3, dfs(3) -> dfs(1) -> dfs(2) 
result = [1, 3]

i=4, dfs(4) -> dfs(6) -> dfs(7) 
result = [1, 3]

i=5, dfs(5) -> dfs(4) -> dfs(6) -> dfs(7) 
result = [1, 3, 5]

i=6, dfs(6) -> dfs(7) 
result = [1, 3, 5]

i=7, dfs(7) 
result = [1, 3, 5]

bfs에 길들여졌더니 이젠 dfs를 모르겠다..... 어렵다. 사이클 문제를 더 연습해봐야겠다.