bamgoesn   2년 전

아무리 생각해도 반례를 모르겠어서 질문 올립니다. 제출번호: 30052504 https://www.acmicpc.net/source... (Go 언어로 작성되어 있습니다)

우선 레드 블루 스패닝 트리 1번은 맞췄습니다. 그런데 2번은 반례를 모르겠는데 틀렸습니다를 받더라고요.

------------------

제 풀이의 로직은, 조건을 만족하는 트리가 존재한다는 전제 하에 아래와 같습니다.

(해결되었으므로 삭제합니다)

별 의미는 없겠지만 18%쯤에서 틀리더라고요.

4번 과정에서 1번에서 제외된 파란 간선은 제외해보는 것도 해봤지만 (제출번호 30052174) 같은 위치에서 오답이 나왔고, 혹시 제 코드에서 출력된 결과가 트리가 아닌 경우가 있나 싶어서 그것도 에러를 고의로 발생시켜 보려는 것으로 시도해봤지만 그건 해당사항이 아니더라고요.

반례를 찾기 위해서 랜덤으로 예제를 만들어서 답안을 검증하는 코드도 따로 짰는데, 예제를 10만 개는 넘게 때려봤는데도 반례가 안 나오더라고요... 그 코드가 또다시 틀린 건지는 모르겠지만...

이쯤 되면 로직이 틀린 게 맞지 않나 싶은데, 혹시 반례를 아시거나 위 로직이 틀린 이유를 아시는 분은 저를 도와주시길 간곡히 부탁드립니다 ㅠㅠ

bamgoesn   2년 전

자답합니다. 반례를 찾았습니다.

4 4 1
B 1 2
R 2 3
R 3 1
B 1 4

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