반응형
문제
1. p = [3,2,7,8,1,4,5,6] => 3
2. p = [2,1,3,4,5,6,7,9,10,8] => 7
풀이
입력으로 들어온 순열로 그래프를 구성하고 그래프 내의 사이클의 개수를 출력하는 문제입니다. DFS를 통해 문제를 해결할 수 있습니다. 매 노드에 대해 DFS 함수를 호출하고 방문 노드를 기록합니다. 사이클이라면 DFS가 종료되고 방문하지 않은 다음 노드에 대해 DFS를 호출합니다. 호출한 DFS 횟수마다 카운트 하면 전체 사이클 개수를 얻을 수 있습니다.
kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.
홍머스 정리
- 난이도: 중
- DFS, 사이클 판별
참조
반응형
'Computer > Coding Test' 카테고리의 다른 글
코딩테스트 문제 (26) - 최대 공약수, 최소 공배수 (0) | 2021.03.10 |
---|---|
코딩테스트 문제 (25) - 텀 프로젝트 (0) | 2021.03.05 |
코딩테스트 문제 (23) - 방향 그래프에서 사이클 찾기 (3) | 2021.03.05 |
코딩테스트 문제 (22) - 랜선 자르기 (0) | 2021.03.05 |
코딩테스트 문제 (21) - 가장 긴 팰린드롬 부분문자열 (0) | 2021.03.02 |