거쳐야만 하는 정점이 모든 정점이 되면 외판원 순회 문제와 다를게 없네요. NP 문제인 듯 합니다
우선 빠른 댓글 무척 감사합니다.
이 문제가 음..
모기업의 프로그래밍 기출(?) 문제입니다.
어차피 테스트케이스도 없지만 저작권 걸릴까봐 문제를 못 올리는게 아쉽네요 ㅠㅠ
거쳐야만 하는 정점은 정점의 수보다 적다고 할 수 있습니다!
예를 들어, 정점의 수가 1000개이면 거쳐야만 하는 정점의 수는 10개라고
할 수 있습니다!
시작점과 거쳐야 하는 점을 모두 모으면 최대 11개입니다. 그들 사이의 최단거리를 모두 구한 다음 그 최단거리로 정점 11개 (또는 그 이하) 짜리 그래프를 재구성하면 외판원 순회가 됩니다.
GCPC라는 대회에 나왔던 A Journey to Greece와 유사합니다.
아아 외판원 순회라는 분류가 있었는지 몰랐습니다.
힌트(?) 주셔서 감사합니다.
이 부분에 대해 몰랐는데 공부해야겠네요!
두 분 감사합니다!
A Journey to Greece 문제도 풀어봐야겠습니다.
우선.. 갑작스러운 태그(?) 죄송합니다.
질문이 하나 더 있어서 댓글 하나 더 써봅니다!
잠깐 공부해본 결과
DP(비트마스크 활용) : O(N!)
완전 탐색 :
O(2NN2)
인 것을 알게되었는데
정점의 수(N)가 무척 많으면(대략 20,000개)
DP로는 풀지 못 한느 외판원 순회 문제인가요?
A Journey to Greece 문제 풀어보려고 했는데, N의 수가 커서 막혔네요 ㅠㅠ
완전 탐색으로는 절대 못 풀 것 같은데..
참고 블로그 : https://hsp1116.tistory.com/40
아 감사합니다! 시간복잡도 DP와 완전탐색 반대로 썼네요... 댓글 감사합니다. N의 뜻을 몰랐습니다.
아아 그래서 '그래프 재구성'이라는 말씀을 하신거군요.. 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
park780172 4년 전
우선... 학교나 학원 과제 그런 것은 아닙니다. 그냥 혼자 공부 중에 막혀서 질문입니다.
그림은 제가 임의로 그린 것입니다.
예를 들어보겠습니다.
간선의 가중치(=정점 사이의 거리)가 모두 1이라고 가정합니다.
위의 양방향 그래프에서 3에서 출발하여,
다시 3으로 돌아올 때 2 4 6을 거쳐야만 한다고 하였을 때 최소 이동거리를 어떤 알고리즘을 사용해야 구할 수 있는지 궁금합니다.
즉, 3 → 2 → 4 → 6 → 3 이런 식의 최소 이동거리입니다. 물론 2 4 6의 방문하는 순서는 상관없습니다.
이런 류의 문제는 어떤 알고리즘을 써야 되는지 잘 모르겠습니다.
BFS, 플로이드같은건 분명 정점과 간선이 많을 때 시간 초과가 날 것 같습니다. 특히, BFS는 반례도 있더군요.
벨만포드와 SPFA도 적용이 안 되니, MCMF도 아닌 것 같습니다.
어떤 방식으로 접근해야 효율적으로 구현할 수 있는지 궁금합니다.
어떤 알고리즘을 써야하는지도 잘 모르겠네요..