[백준] 2668 숫자고르기 python 풀이

문제

• 난이도: 골드5
• 알고리즘 분류: 깊이 우선탐색
• 요약: 첫째 줄의 집합과 둘째 줄의 집합을 이루는 수가 일치하면서 최대한 많은 수를 뽑을 때, 뽑힌 정수들에 대한 정보 출력하기

 

풀이

입력 정보를 받아 그래프를 만들고 사이클이 발생하는 노드를 알아내어 문제를 해결한다. 이를 위해 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] = []

 

 

 

dfs 함수

 

dfs 함수는 현재 노드 v와 시작 노드 i를 매개변수로 받고, 재귀를 돌면서 사이클이 발생하는 노드를 저장한다. 이때, visited 배열을 통해 방문 여부를 체크하여 사이클이 존재함을 확인할 수 있다.

어떤 노드(v)의 모든 이웃 노드(nv)에 대해

• nv를 아직 방문하지 않았으면 재귀적으로 dfs를 호출한다.
• nv를 이미 방문했고 nv가 시작 노드 i라면 사이클이 형성되었으므로 res 리스트에 nv를 추가한다.

 

 

코드

N = int(input())

graph = [[] for _ in range(N+1)]
for idx in range(1, N+1):
    v = int(input())
    graph[v].append(idx)

def dfs(v, i): # 현재 노드, 시작한 노드
    visited[v] = True

    for nv in graph[v]:
        if visited[nv] == False:
            dfs(nv, i)
        elif visited[nv] == True and nv == i:
            res.append(nv)

res = []
for i in range(1, N+1):
    visited = [False] * (N+1)
    dfs(i, i)

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