[파이썬][백준 2668][💛골드 5] (dfs)
Categories: BOJ
Tags: BOJ Coding Test Python Algorithm
🧞♂️ 난이도
💛 골드 5
🧞♂️ 문제
숫자 고르기
🧞♂️ 유형
dfs
🧞♂️ 내 풀이
첫째 줄의 숫자들은 index, 두번째 줄 숫자들은 value 라고 생각하고 풀었다. 그래서 dfs을 이용해서 index -> value 로 비교를 하고, 그 다음 dfs 에는 index 자리에 value를 넣으면서 탐색을 한다.
문제를 풀어보고나니까 이게 그냥 사이클을 찾는 문제였던것 같다.
역시 다른 사람의 풀이를 검색해보니까 그래프에서 사이클을 찾는 방법으로 풀었다. 그냥 visited으로 방문 노드를 체크하면서, 이미 방문했던 노드를 방문하면 사이클이 일어난것으로 생각하고 푸는 방법도 있는것 같다.
아 그리고 set를 사용할 수 있는 이유는, 어차피 첫째줄은 고유한 숫자들이고 중복이 일어날 일이 없어서, 그냥 set 으로 확인이 가능하다.
🧞♂️ 파이썬 풀이
import sys
input = sys.stdin.readline
N = int(input())
values = [0]
for _ in range(N):
values.append(int(input()))
answer = set()
def dfs(index, first, second):
first.add(index)
second.add(values[index])
if arr[index] in first:
if first == second:
answer.update(first)
return
return dfs(values[index], first, second)
for i in range(1, N+1):
if i not in answer:
dfs(i, set(), set())
print(len(answer))
for num in sorted(list(answer)):
print(num)
🧞♂️ 다른 사람 파이썬 풀이
https://cotak.tistory.com/141 사이클 풀이법
import sys, collections
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input().rstrip())
graph = collections.defaultdict(list)
for i in range(1, N+1):
graph[int(input().rstrip())].append(i)
def dfs(index, visited):
visited.add(index)
checked[index] = 1
for v in graph[index]:
if v in visited:
result.extend(list(visited))
return
else:
dfs(v, visited.copy())
checked = [0 for _ in range(N+1)]
result = []
for i in range(1, N+1):
if not checked[i]:
dfs(i, set([]))
result.sort()
print(len(result))
for num in result:
print(num)