Blog Content

  • [그래프/문제] BOJ9466, 텀프로젝트 알고리즘, DFS Cycle

    Category 개발레시피/└ Algorithm on 2017. 5. 28. 13:36

    문제 : https://www.acmicpc.net/problem/9466 문제문제는 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께 하고 싶은 학생들을 선택하는데어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제이다. 풀이이 문제는 DFS를 활용하여 Cycle을 이루는지 확인하는 방법으로 문제를 풀 수 있다.DFS를 하다가, 싸이클이 발생하는 조건을 찾을 수 있다.정점 방문을 시작했는지 체크하는 visited 배열,그 정점의 방문함수가 완전히 끝났는지를 체크하는 finished 배열이 필요햐다. 다음에 방문할 정점을 k라고 했을때, visited[k] = true, finished[k] = false인 경우이다.예를들어 1->2->3->1 이 싸이클을 이룬다고 가정해보자.1번 정..

    Read more