백준 2668번 파이썬 문제풀이(숫자고르기)

---

해당문제는 그래프문제이다. 사실 이것이 그래프 문제라는 것을 발견하지 못한다면 굉장히 어렵게 풀 수도 있다. 위아래의 숫자중 위의 숫자가 부모 아래숫자가 자식 노드라고 생각하면 되며 싸이클을 도는 집합이 몇개 있는지를 찾는 문제이다. 그리고 그 집합의 원소들을 오름차순으로 출력하는 문제이다. 즉, 여기서 말하는 싸이클이란 1이란 숫자를 뽑았을 때 자식의 숫자를 쭉쭉 따라가다가 결국 1이 나오면 싸이클이라고 할 수 있다. 즉 처음에 뽑은 숫자가 나와야한다. 해당 문제를 2가지 방법으로 구현해봤다. 

 

1. visited 배열을 한번만 만들어서 처리하기(즉, 싸이클이 된 집합의 원소들만 True로 방문처리를 설정하여 검색해야하는 탐색의 수를 줄이는 방법) 

N = int(input())
graph = [[] for _ in range(N + 1)]
count = 0  # 결과를 출력할 개수
result = []  # 집합을 저장할 리스트
visited = [False] * (N + 1)  # 방문처리
for i in range(N):
    a = int(input())
    if i + 1 == a:  # 만약 이미 카드가 같다면 해당 카드를 바로 뽑으면 되므로
        count += 1  # 개수를 1증가한 후
        result.append(a)  # 해당 카드를 저장
        visited[a] = True  # 방문처리

    graph[i + 1].append(a)  # i+1 -> a 로 그래프를 등록해준다.


def dfs(v, start, cnt):
    global count

    if cnt != 0 and v == start:  # 만약 뽑은개수가 0이 아니고 출발점과 같다면
        count += cnt  # 개수를 1증가
        for x in temp:  # 저장된 집합을 돌면서
            result.append(x)  # 집합의 원소를 저장해 준다.
        return True  # 그 후 True저장

    for i in graph[v]:  # 해당 그래프와 연결된 카드를 돌면서
        if not visited[i]:  # 만약 방문하지 않았다면
            visited[i] = True  # 해당 카드 방문처리
            temp.append(i)  # 해당 카드 저장
            if not dfs(i, start, cnt + 1):  # 만약 False를 반환했다면(집합이 사이클을 돌지 않는다면)
                visited[i] = False  # 다시 방문처리 해제
            else:  # 만약 True라면(싸이클을 돈다면)
                return True  # 계속해서 True반환
    return False


for i in range(1, N):
    if not visited[i]:  # 만약 방문하지 않았다면 dfs를 돈다.
        temp = []  # 싸이클을 형성하는 집합의 원소를 담을 temp리스트 선언
        dfs(i, i, 0)  # dfs를 돈다.

result.sort()  # 오름차순정렬 후 출력

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

2. 1차원 리스트의 인덱스 - 저장된 숫자를 == 위 - 아래 숫자로 설정하여 dfs를 돌리는 방식

 

n = int(input())
arr = [0] + [int(input()) for i in range(n)]


def dfs(cur, start):
    visited[cur] = True

    if arr[cur] == start:
        return True

    if visited[arr[cur]]:
        return False

    return dfs(arr[cur], start)


cnt = 0
ans = []
for i in range(1, n + 1):
    visited = [False for i in range(n + 1)]

    if dfs(i, i):
        cnt += 1
        ans.append(i)

print(cnt)
for i in ans:
    print(i)