[백준 2668번] 숫자 고르기

박형진·2022년 12월 27일
0

https://www.acmicpc.net/problem/2668


1. DFS return값 활용 풀이

from collections import defaultdict
import sys


def dfs(key, visited):
   if d[key] == start:
       return visited
   if d[key] not in visited:
       visited.add(d[key])
       return dfs(d[key], visited)
   return False


n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
   d[i] = int(sys.stdin.readline().rstrip())

ans = []
for i in range(1, n+1):
   start = i
   result = dfs(start, set([i]))
   if result:
       ans.extend(result)

x = sorted(set(ans))
print(len(x))
for i in x:
   print(i)

2. DFS 외부 리스트에 값 추가 풀이

from collections import defaultdict
import sys


def dfs(key, visited):
    if d[key] == start:
        for v in visited:
            ans.add(v)
    if d[key] not in visited:
        visited.add(d[key])
        dfs(d[key], visited)
    # return None


n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
    d[i] = int(sys.stdin.readline().rstrip())

ans = set()
for i in range(1, n+1):
    start = i
    dfs(start, set([i]))
    
x = sorted(list(ans))
print(len(x))
for i in x:
    print(i)

시작한 KEY값으로 다시 돌아오는 싸이클을 가질 경우, visited에 속하는 모든 KEY값들을 답에 추가한다.


3. visited 코드

from collections import defaultdict
import sys


def dfs(key, cycle):
    visited[key] = True

    if visited[d[key]]:
        if d[key] in cycle:
            left = cycle.index(d[key])
            for c in cycle[left:]:
                used.add(c)
    else:
        cycle.append(d[key])
        dfs(d[key], cycle)

n = int(input())
d = defaultdict(int)
for i in range(1, n + 1):
    d[i] = int(sys.stdin.readline().rstrip())

visited = [False] * (n+1)
used = set()
for start in range(1, n + 1):
    if not visited[start]:
        dfs(start, [start])

print(len(used))
for i in sorted(used):
    print(i)

텀 프로젝트 문제와 동일한 풀이 방식이다.

주어진 N이 만만하다면 직관적인 2번째 풀이 코드를 사용해도 되지만, 텀 프로젝트 문제처럼 N이 큰 값으로 주어진다면 이 풀이를 사용하자.

싸이클 문제의 경우 key값으로 나타내지는 노드들은 단 한번만 방문하면 싸이클 여부를 판단할 수 있다.

profile
안녕하세요!

0개의 댓글