[백준] [DFS] 2668. 숫자고르기

2668. 숫자고르기

2668번: 숫자고르기

 

• 내 풀이
  • 테케는 맞지만 오답

n=int(input())
lst=[i for i in range(n+1)]
tmp={}
tmp[0]=0

def union(x,y):
    xroot=find(x)
    yroot=find(y)
    if (xroot<yroot):
        lst[yroot]=xroot
    else:
        lst[xroot]=yroot

def find(x):
    if x!=lst[x]:
        lst[x]=find(lst[x])
    return lst[x]

for i in range(1,n+1):
    m=int(input())
    tmp[i]=m


for idx,v in list(tmp.items()):
    if idx==0:
        continue
    for i in lst:
        if v==i and idx==list(tmp.values())[i]:
            union(idx,v)

mcount=0
maxInt=[]
for i in lst:
    if i==0: continue
    if lst.count(i)<mcount: continue
    if i in maxInt: continue
    if lst.count(i)>mcount:
        mcount=lst.count(i)
        maxInt.clear()
    maxInt.append(i)
      
c=0
result=[]

for mi in maxInt:
    for idx, i in enumerate(lst):
        if idx==0:
            continue
        if i==mi:
            c+=1
            result.append(idx)
        elif idx==list(tmp.values())[idx]:
            c+=1
            result.append(idx)
  
print(c)
print(*sorted(result), sep="\n")

 

• 다른 사람 풀이
  • dfs

N = int(input())			
lst=[0]
for _ in range(N):
   lst.append(int(input()))
answer = set()

# dfs 정의
def dfs(num):
    first.add(num)			
    second.add(lst[num])
  
    if lst[num] in first:	# 이어졌던 값 중 lst[num]이 있을 때
        if first == second:		# 첫번째 줄 집합과 두번째 줄 집합이 같으면 사이클
            answer.update(first)	# 결과 업데이트
            return True
          
        return False
    return dfs(lst[num])	# 두번째줄 값 이어서 탐색

# dfs 실행
for i in range(1, N+1):
    if i not in answer:		# 결과에 없을 경우만
        #집합 초기화
        first=set()
        second=set()
        dfs(i)

print(len(answer))
#리스트 한번에 출력하는 방법: print(*list)
print(*sorted(list(answer)), sep="\n")