skqoaudgh   5년 전

저는 큐를 이용해서 문제를 풀었습니다.

알고리즘은 아래와 같습니다.

  1. 다른 사람들로부터 지목을 받지 못한 인덱스를 큐에 넣는다.
  2. 큐에서 하나씩 꺼내 가리키는 인덱스의 "지목받은 수" 를 -1 한다.
  3. -1 한 수가 0이라면 해당 인덱스도 큐에 넣는다.
  4. 반복

알고리즘에 문제가 있는걸까요? 도움 부탁드립니다.

예외케이스도 부탁드리겠습니다.

rhs0266   5년 전

위상정렬 알고리즘의 queue 버전을 응용하여 사이클에 포함되지 않는 정점을 찾는 매우 훌륭한 풀이입니다.

하지만, test case가 있는 문제에서는 항상 사용하는 변수들의 적절한 초기화가 중요합니다. cnt[] 를 초기화 하세요.

rhs0266   5년 전

추가로 조언드리고 싶은 부분은, 이 문제와 같이 입출력 (이 문제는 입력만) 의 총 크기가 방대할 경우에는 cin, cout 보다 scanf, printf 가 훨씬 빠릅니다. 한 번 앞서 말씀 드린 버그를 수정하여 제출해보시고, scanf, printf로 바꾼 버전도 시도해보시면 좋은 경험이 되실 것 같습니다.

skqoaudgh   5년 전

초기화를 해주어서 문제를 해결할 수 있었습니다. 정말 감사합니다!

조언해주신 부분도 한 번 시도해보도록 하겠습니다. 도움주셔서 정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.