dfs (1) 썸네일형 리스트형 백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 그래프 탐색과 DFS의 혼종이다. 그래프에 Cycle이 있는지 점검하는 문제다. 무식하게 풀자면 모든 노드를 DFS 돌려서 자기 자신으로 돌아오는 지 체크하면 된다! 근데 중복이 엄청 많을 것이다. 아무리 시간 복잡도가 3초라도 이런건 무조건 시간초과다 메모이제이션을 통해 최대한 중복 체크를 줄인다! 각 노드의 상태는 둘로 나뉜다. 1. 이전 DFS에서 방문한 노드 - Cycle 못 만든다. 2. 이번.. 이전 1 다음