240321 [BOJ/백준] 2668. 숫자고르기

 

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

2668번: 숫자고르기

---

나의 코드

def dfs(x):   # 싸이클 유무 확인 함수
    global check
    for w in adjl[x]:
        if w == k:  # 처음 수와 마지막 수가 같다면(싸이클이 존재한다면)
            check = True
            return
        if visited[w] == 1:
            continue
        visited[w] = 1
        result.append(x)
        dfs(w)


N = int(input())
adjl = [[] for _ in range(N+1)]
for j in range(1, N+1):
    adjl[j].append(int(input()))

ans = []

for k in range(1, N+1):  # adjl의 인덱스값과 value값이 같을 경우
    if k == adjl[k][0]:
        ans.append(k)

for k in range(1, N+1):
    visited = [0]*(N+1)
    check = False
    result = []
    dfs(k)
    if check:
        ans.extend(result)

ans = list(set(ans))  # 중복제거를 위해 set씀
ans.sort()
print(len(ans))
for z in ans:
    print(z)

 

결과

---

처음에 싸이클이 하나만 있을거라고 생각해서 처음부터 주어진 입력 외에도 싸이클이 존재하는 반례를 찾아서 코드를 짰다. 근데 4프로에서 바로 탈락이 되었고 그 이후에 계속 수정했으나 틀렸다..ㅜㅜ

내가 짠 함수로는 싸이클이 있을 경우 2개씩 표현이 되었고 그래서 set함수로 중복제거하며 맞는 코드를 짤 수 있었다.

set말고 다른 방법이 없을까해서 찾아봤는데 기본적으로 알고 있는 if i not in ans: 의 방법 말고 다른 것은 찾을 수 없었다. 

일단 이 문제에서 배운 것은 아주 기본적인 두가지가 있다.

1. 아주 기초적인 extend메서드를 까먹고 append로만 구현하려고 했던 것! extend메서드를 다시 한 번 생각해 볼 수 있었다. 

2. visited와 result의 초기화! 다른 방법으로 초기화했었는데 for문 안에서 조금 더 간결하게 초기화 할 수 있었다.

오늘 공부 끄으으읏!!