[백준 2668번] 숫자 고르기 문제 풀이 (with Python)

 

< 문제 >

 

 

 

< 입출력 >

 

 

 

 

< 풀이 >

첫번째 줄 집합과 두번째 줄 집합을 만든다. 

arr을 두번째 줄이라 할때, 1번부터 N번까지 순서대로 돌며, arr[num]이 첫번째 줄 집합에 있는지 확인하여 있다면, 

첫번째 줄 집합과 두번째 줄의 동등비교를 한다.

만약 두 집합이 동일하면 answer을 업데이트 해준다.

하지만, 동일하지 않다면, 첫번째 집합과 두번째 집합의 개수가 달라지므로 False를 통해 탐색을 중단한다.

 

< 첫번째 예시 입력 시>

first= {1} second= {3}
dfs
first= {1, 3} second= {1, 3}
True
first= {2} second= {1}
dfs
first= {1, 2} second= {1, 3}
dfs
first= {1, 2, 3} second= {1, 3}
False
first= {4} second= {5}
dfs
first= {4, 5} second= {5}
False
first= {5} second= {5}
True
first= {6} second= {4}
dfs
first= {4, 6} second= {4, 5}
dfs
first= {4, 5, 6} second= {4, 5}
False
first= {7} second= {6}
dfs
first= {6, 7} second= {4, 6}
dfs
first= {4, 6, 7} second= {4, 5, 6}
dfs
first= {4, 5, 6, 7} second= {4, 5, 6}
False

 

 

 

< 코드 >

N = int(input())
arr = [0]   # 두번째 줄
for _ in range(N):
    arr.append(int(input()))
answer = set()

# dfs 정의
def dfs(first, second, num):
    first.add(num)
    second.add(arr[num])
    if arr[num] in first:   # arr[num]이 첫번째 줄 집합에 이미 있을 때
        if first == second:
            answer.update(first)
            return True 
        return False   # 개수가 달라지므로, False 반환하고 종료
    return dfs(first, second, arr[num])

for i in range(1,N +1):
    if i not in answer:
        dfs(set(), set(), i)

print(len(answer))
print(* sorted(list(answer)), sep='\n')