cns 2번 뭐냐

[익명(39.114)]

외판원 순회야?

[익명(121.131)]

그 은행 도는거 말하는거임? 나는 최소신장트리 써서 풀었는데

[익명(39.114)]

어케? 같은곳 방문 안되잖아

[익명(118.235)]

출발지가 2갠데 어떻게 mst?

[익명(121.131)]

최소신장트리 연결하기 전에 우선 출발지 두개끼리 연결되어 있으면 그건 제외함. 그 다음, 최소신장트리 구성하고나서 가장 cost가 긴 루트 하나만 빼줬음. 그렇게하면 모든 곳을 다 순회하면서 서로 겹치지 않도록 만들어지지 않음? 그 두개에서 뭐 어케 출발하든 간에 최소 cost로 한번씩만 찍으면 되니까

[익명(118.235)]

그거 ㅅㅂ 첨에 다익스트라 쓰면 될줄알고 했는데 계속 이동하면서 순회하는거여서 플로이드 워샬 씀

[익명(39.114)]

워샬인가?

[익명(118.235)]

N이 최대 10갠가 그거밖에 안되잖아 워셜써서 테이블 만들고 pos1이랑 pos2가 갈 수 있는 곳 중에 제일 거리 가까운애들부터 움직였음 그거 한번 간 데 다시 못가고, 서로 갔던데 못간다고 하고, 무조건 갈 수 있게 연결되어있다고 해서 그렇게 해도 될거같더라.. 흠

[익명(39.114)]

Y자로 연결되면 반례 아님?

[익명(118.235)]

나도 그래서 좀 찜찜함 그런 특이케이스 분명히 있을거같아서.. 근데 백트래킹이나 완전탐색으로 풀려니까 도저히 못하겠어서 하..

[익명(118.235)]

나도 그 y자처럼 갔다가 다시 돌아와야하는 경우도 있지 않을까 했는데 한번 방문했던곳은 재방문 하지 않는다고 명시되있길래 그런 경우는 없겠구나 했음