✓

태그:

CLASS 5 ESSENTIAL

'노드를 방문했다'와 '노드가 사이클을 이룬다' 2개의 정보가 필요할 것 같아요…!!

풀이 비스무리한거 보기

학생들에게 프로젝트에 함께하고 싶은 학생 번호를 선택하고, 이 지명 관계가 사이클을 이뤄야만 조가 편성될 때, 조에 속하지 못하는 학생 수를 구하는 문제입니다. 먼저 문제의 조건을 살펴보면, 학생을 노드로 하고 지명 관계를 방향성 그래프로 나타낼 수 있고, 학생 한 명당 한 명을 지목할 수 있으므로 각 노드에서 나가는 간선은 오직 1개입니다. 이것을 생각해보면 어떤 노드가 사이클을 이룬다면 그것은 유일해야 합니다. 이것을 이용하여 문제를 해결하는 방법을 떠올릴 수 있겠습니다.

먼저, 아무 학생에서나(편의상 번호 순서대로) 출발하여 지나간 노드를 모두 방문했다고 표시하고, 이미 방문했다고 표시한 노드를 만났을 경우 탐색을 멈춥니다. 이 때 2가지 경우가 있을 수 있는데, 한 가지는 사이클을 이루었는지 확인한 노드인 경우와 그렇지 않은 경우입니다. 전자는 사이클을 이룬 노드라면 이미 해당 사이클에 속한 모든 노드가 사이클에 속함을 확인했기 때문에 지금까지 방문했던 노드는 모두 사이클을 이루지 않고, 이루지 않았다면 당연하게도 지금까지 방문했던 노드도 모두 사이클을 이루지 않습니다. 따라서 전자의 경우는 지금까지 방문했던 노드는 사이클을 이루지 않는다고 저장하면 됩니다. 이제 후자의 경우입니다. 후자는 지금까지 방문했던 노드 중 사이클을 이루는지 확인한 노드가 없는 상태인데, 방문했던 노드 중 하나를 다시 방문했다면 지금까지 탐색한 경로에 사이클이 존재하는 것입니다. 또한, 해당 노드는 사이클에 속하는 노드가 됩니다. 따라서 방문하기 시작한 노드부터 해당 노드 직전까지는 사이클에 속하지 않음을, 해당 노드가 포함된 사이클에 속한 노드는 사이클에 속함을 표시하면 됩니다. 이를 모든 노드에 대해 적용 후, 사이클에 속하지 않는다고 표시된 노드의 개수를 출력하면 됩니다. 이해가 안되는데요

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-05 12:29:09

---