문제 링크이다.
https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=
www.acmicpc.net
사이클을 탐색할 수 있으면 해결할 수 있는 문제이다.
팀이 결정되는 조건이 결국 사이클을 이루는 조건이기 때문이다.
사이클을 검사할 때 템플릿처럼 활용할 수 있을 것 같다.
먼저 방문처리 배열을 두 개를 둔다.
vis배열은 0인 경우 아예 방문을 하지 않은 것이고, -1인 경우에는 방문을 했고, 더 이상 방문할 필요가 없다는 것이다.
1인 경우에는 현재 방문 중이라는 의미이다.
Done배열은 사이클을 이루는 성분인지 여부를 저장한다.
만약 학생 x를 한번 방문해서 vis[x]가 1인 상태라고 해보자. 즉 방문하고 있는 중이라는 것인데,
이 상태에서 x를 누군가가 또 방문한다는 것은? 학생 1을 포함하는 사이클이 존재한다는 의미이다.
따라서 x는 사이클이라는 것이 확실하기 때문에 done[x]를 true로 설정해준다.
그리고 cycle 검사를 마치면 (재귀를 탈출하면) 더 이상 방문할 필요가 없다는 의미이기 때문에 vis[x]를 -1로 만들어준다.
결과적으로 cycle검사의 탈출 조건은 이미 방문할 필요가 없는 곳이거나(vis가 -1인 경우)
이미 사이클을 이루고 있는 경우(Done이 1인 경우)인 것이다.
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 2667번: 단지번호붙이기 (DFS) (C++) (0) | 2019.07.18 |
|---|---|
| 백준 2667번: 단지번호붙이기 (C++) (0) | 2019.07.18 |
| 백준 15655번: N과 M (6) (C++) (0) | 2019.07.17 |
| 백준 15652번: N과 M (5) (C++) (0) | 2019.07.17 |
| 백준 1697번: 숨바꼭질 (C++) (0) | 2019.07.17 |