반응형
문제
1. p = [3,1,3,7,3,4,6], N = 7
=> 3
2. p = [1,2,3,4,5,6,7,8], N = 8
=> 0
풀이
입력을 통해 그래프를 구성하고 사이클에 속하지 않은 정점들의 개수를 출력하는 문제입니다. DFS를 통해 노드를 재귀적으로 방문하면서 리스트를 채워주고 이미 방문한 정점에 도달했을 때, 그 시작점부터의 리스트를 반환하면 사이클에 속한 정점을 구할 수 있습니다. 이를 전체 노드 수에서 빼주면 답을 구할 수 있습니다.
kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.
홍머스 정리
- 난이도: 중
- DFS를 이용한 그래프 사이클 판별
참조
반응형
'Computer > Coding Test' 카테고리의 다른 글
코딩테스트 문제 (27) - 리스트에서 부분집합 출력하기 (0) | 2021.06.11 |
---|---|
코딩테스트 문제 (26) - 최대 공약수, 최소 공배수 (0) | 2021.03.10 |
코딩테스트 문제 (24) - 순열 사이클 (0) | 2021.03.05 |
코딩테스트 문제 (23) - 방향 그래프에서 사이클 찾기 (3) | 2021.03.05 |
코딩테스트 문제 (22) - 랜선 자르기 (0) | 2021.03.05 |