4803번 - 트리
안녕하세요
4803 문제 풀다가 제 나름 테스트케이스라고 생각하고 풀다가 의문이 생겼습니다
다음과 같은 테스트케이스는 안되나요?
같은 간선이 없고 저 경우에는 트리가 없어야 한다고 생각하는데
정답코드로 실행하면 트리가 하나 있다고 나오네요
제 생각이 틀린건지 문제가 틀린건지 알려주시면 감사하겠습니다!
트리가 하나 있는 것이 맞습니다.
이 테스트케이스는 세 개의 정점이 1-2-3 형태로 연결되어 있는 것이고, 이는 사이클이 없는 연결요소를 1-2-3 하나 가지므로 트리가 하나 있게 됩니다.
사이클이 없는 조건을 만족하면 트리가 되는거였군요!
제가 잘 몰라서그런데 혹시 하나의 정점이 두개이상의 부모노드를 가져도 괜찮은건가요?
정점이 루트가 아닌 이상 루트가 아닌 이상 하나의 정점은 반드시 하나의 부모를 가집니다.
하지만 트리의 부모자식 관계는 루트가 무엇인지에 따라 결정되며, 문제에서 간선을 a b라고 주었다 할지라도 a가 부모, b가 자식(혹은 그 반대)이라는 보장은 없습니다.
예를 들어서 1-2-3 형태의 트리에서 1이 루트면 2의 부모가 1, 3의 부모가 2가 되지만 2가 루트라면 1과 3 모두 2를 부모로 가집니다.
친절한 답변 감사드립니다!
댓글을 작성하려면 로그인해야 합니다.
deliciousqoo 2년 전
안녕하세요
4803 문제 풀다가 제 나름 테스트케이스라고 생각하고 풀다가 의문이 생겼습니다
다음과 같은 테스트케이스는 안되나요?
같은 간선이 없고 저 경우에는 트리가 없어야 한다고 생각하는데
정답코드로 실행하면 트리가 하나 있다고 나오네요
제 생각이 틀린건지 문제가 틀린건지 알려주시면 감사하겠습니다!