[백준] 2668번 숫자고르기 (파이썬)

 

문제

 

2668번: 숫자고르기

 

 

정답 소스코드 (Python)

 

def dfs(vert,start):
    visited[vert]=True
    value=field[vert]
    if not visited[value]:dfs(value,start)
    elif visited[value] and value==start:result.append(value)

n=int(input())
field=[0]
result=[]
for i in range(n):field.append(int(input()))

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

result.sort()
print(len(result))
for ele in result:print(ele)

 

풀이  (Python)

 

첫 풀이의 경우 아래와 같이 조합 라이브러리를 사용하여 풀이를 진행했었다.

import sys
sys.setrecursionlimit(10**6)

from itertools import combinations

n=int(input())
field=[]
for i in range(n):field.append(int(input()))
result=[]

def check(test):
    compare_test=[]
    for ele in test:compare_test.append(field[ele-1])
    if set(test)==set(compare_test):return True
    else: return False

for i in range(n-1,0,-1):
    combi=list(combinations([j for j in range(1,n+1)],i))
    for ele in combi:
        tmp=[]
        if check(ele):
            tmp.append(len(ele))
            tmp.append(ele)
            result.append(tmp)

max_len,ans=max(result)
print(max_len)
print(*ans,sep="\n")

 

위와 같이 풀이 시 문제점들은 , 정답은 맞힐 수 있지만 메모리초과 문제를 겪게 된다. 

 

이를 해결하기위해 습관적으로 재귀깊이를 조절하는 sys.setrecursionlimit(10**6) 를 사용하였지만, 재귀를 사용하지 않는 풀이 이기 때문에, 의미가 없는 코드였다.

 

과연 메모리 초과는 어디에서 발생했을까?

리스트의 길이가 너무 길게 되면 발생할 수 있는 메모리 문제에 포커싱하여 보면, combination으로 나올 수 있는 가짓수가 너무 많아질 수 있다는 결론에 도달했다.

 

다시 처음부터 풀이를 생각해 보았을 때 문제의 정답은, 윗줄의 집합과 아랫 줄의 집합이 일치하면 된다.

이는 윗줄에서 아랫줄로 아랫줄에서 윗줄로 가는 그래프 구조에서 사이클을 확인하면 정답과 일치한다.

 

첫 로직에서는 union-find구조를 생각했었지만, 이는 무방향 그래프에서 적용되는 알고리즘이다.

문제의 경우 방향성 그래프 구조이기 때문에 BFS로 풀이하여야 한다.

 

Point 1)  BFS로직

def dfs(vert,start):
    visited[vert]=True
    value=field[vert]
    if not visited[value]:dfs(value,start)
    elif visited[value] and value==start:result.append(value)

 

1. 해당 정점을 방문한 이후 방문체크를 한다.

2. 다음 정점이 방문하지 않았던 정점인 경우  DFS진행

3. 다음 정점이 방문했었던 정점이면서 시작점이 같다면 result리스트에 결과 값 추가

 

이로써 모든 방향 그래프에서의 사이클인 경우 result에 추가되어 풀 수 있었던 문제이다.