cokcjswo   6년 전

아무리 생각해도 답을 모르겠어서

최소스패닝 트리를 답으로 찍었는데 맞네요


근데, 최소스패닝 트리는 분명히 경로가 아니라고 알고 있습니다. (경로인 최소스패닝 트리도 있겠지만...)

https://ko.wikipedia.org/wiki/%EA%B2%BD%EB%A1%9C_(%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0)    


하지만 

문제에서는 애초에 사심 경로라는 말에 경로가 들어가며

- 이 경로는 3가지 특징을 가지고 있다.

- 경로를 구성한다.

- 경로를 만들 수 있다.

- 경로이다.

등의 표현을 사용하고 있는데

(혹 사심경로가 경로라는 말이 들어가지만 경로가 아닌 전혀 다른 새로운 정의라면 저 표현들에서도 사심경로라는 단어를 써야 겠죠.)

답이 최소스패닝 트리라니..

제가 뭔가 놓치고 있나요?


차라리 이름으로 간선 모음 정도가 더 알맞지 않나싶습니다. (이것도 이상한 이름이지만)

- 이 간선 모음을 이용해서 임의의점에서 임의의점으로 가는 경로를 설정할 수 있다. 이건 맞겠지만 애초에 저 간선 모음을 경로라고 하는건 이상한거같아요.


혹시 경로가 맞는데 테스트케이스가 약해서 MST를 출력해도 맞는건가요?


글의 두서가 없네요 죄송합니다.

부족한 부분 지적 해주시면 감사하겠습니다.

jh05013   6년 전

트리가 아니라 경로라면 존재성을 판별하는 것조차 NP-Hard입니다. 같은 종류의 학교를 연결하는 간선을 다 제거하면 이분 그래프가 되는데, 이 조건으로 임의의 이분 그래프를 만들 수 있으므로 일반적인 이분 그래프에서 해밀턴 경로를 찾는 문제가 됩니다. 용어가 좀 이상한 것 같습니다.

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