[백준/Python] 2668번(그래프, DFS)_숫자고르기

📌문제 유형

그래프 이론, 그래프 탐색, DFS (골드5)

 

📌문제

2668번: 숫자고르기

 

📌나의 문제풀이

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

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

def dfs(x):
    global v1
    global v2

    v1[x] = 1
    
    if v2[graph[x][0]] == 0:
        v2[graph[x][0]] = 1
        dfs(graph[x][0])
    return

ans = []
for i in range(1,n+1):
    v1 = [0 for _ in range(n+1)]
    v2 = [0 for _ in range(n+1)]

    dfs(i)

    if v1 == v2:
        for n in range(len(v1)):
            if v1[n] == 1:
                ans.append(n)

ans = list(set(ans))
ans.sort()
print(len(ans))
for num in ans:
    print(num)

 

📌 다른사람의 문제풀이

[백준-파이썬] 2668: 숫자 고르기

import sys

input = sys.stdin.readline

N = int(input())

adj = [[] for _ in range(N + 1)]

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


# DFS로 탐색하다가 사이클 발생한 것들을 다 더하면 된다 !!

def dfs(num):
    if visited[num] == False:
        visited[num] = True
        for a in adj[num]:

            tmp_up.add(num)
            tmp_bottom.add(a)

            if tmp_up == tmp_bottom:
                ans.extend(list(tmp_bottom))
                return

            dfs(a)
    visited[num] = False


ans = []

for i in range(1, N + 1):
    visited = [False] * (N + 1)  # 위에 값 기준으로
    tmp_up = set()
    tmp_bottom = set()

    dfs(i)

ans = list(set(ans))
ans.sort()

print(len(ans))
for a in ans:
    print(a)

 

📌 리뷰 

- visited 함수 잘 활용하기 

- 위, 아래 같은거 확인하고 리스트를 늘릴 수도 있음