park780172   4년 전

f4c1abb2-efbb-4791-ae78-199fc478fa5c




우선... 학교나 학원 과제 그런 것은 아닙니다. 그냥 혼자 공부 중에 막혀서 질문입니다. 

 그림은 제가 임의로 그린 것입니다. 

 예를 들어보겠습니다. 

 간선의 가중치(=정점 사이의 거리)가 모두 1이라고 가정합니다. 

 위의 양방향 그래프에서 3에서 출발하여, 

다시 3으로 돌아올 때 2 4 6을 거쳐야만 한다고 하였을 때 최소 이동거리를 어떤 알고리즘을 사용해야 구할 수 있는지 궁금합니다. 

즉, 3 → 2 → 4 → 6 → 3 이런 식의 최소 이동거리입니다. 물론 2 4 6의 방문하는 순서는 상관없습니다.  

이런 류의 문제는 어떤 알고리즘을 써야 되는지 잘 모르겠습니다.

 BFS, 플로이드같은건 분명 정점과 간선이 많을 때 시간 초과가 날 것 같습니다. 특히, BFS는 반례도 있더군요. 

 벨만포드와 SPFA도 적용이 안 되니, MCMF도 아닌 것 같습니다.

 어떤 방식으로 접근해야 효율적으로 구현할 수 있는지 궁금합니다.

어떤 알고리즘을 써야하는지도 잘 모르겠네요..



jwvg0425   4년 전

거쳐야만 하는 정점이 모든 정점이 되면 외판원 순회 문제와 다를게 없네요. NP 문제인 듯 합니다

park780172   4년 전

@jwvg0425

우선 빠른 댓글 무척 감사합니다.

이 문제가 음..

모기업의 프로그래밍 기출(?) 문제입니다.

어차피 테스트케이스도 없지만 저작권 걸릴까봐 문제를 못 올리는게 아쉽네요 ㅠㅠ

거쳐야만 하는 정점은 정점의 수보다 적다고 할 수 있습니다!

예를 들어, 정점의 수가 1000개이면 거쳐야만 하는 정점의 수는 10개라고

할 수 있습니다!

jh05013   4년 전

시작점과 거쳐야 하는 점을 모두 모으면 최대 11개입니다. 그들 사이의 최단거리를 모두 구한 다음 그 최단거리로 정점 11개 (또는 그 이하) 짜리 그래프를 재구성하면 외판원 순회가 됩니다.

GCPC라는 대회에 나왔던 A Journey to Greece와 유사합니다.

jh05013   4년 전

다만 A Journey to Greece와 달리 거쳐야 하는 점이 10개라서 O(2NN2)가 아닌 O(N!)로 외판원 순회를 풀어도 됩니다.

park780172   4년 전

@jh05013

아아 외판원 순회라는 분류가 있었는지 몰랐습니다.

힌트(?) 주셔서 감사합니다.

이 부분에 대해 몰랐는데 공부해야겠네요!

두 분 감사합니다!

A Journey to Greece 문제도 풀어봐야겠습니다.

park780172   4년 전

@jh05013

우선.. 갑작스러운 태그(?) 죄송합니다.

질문이 하나 더 있어서 댓글 하나 더 써봅니다!

잠깐 공부해본 결과

DP(비트마스크 활용) : O(N!)
완전 탐색 :  O(2NN2)

인 것을 알게되었는데

정점의 수(N)가 무척 많으면(대략 20,000개)

DP로는 풀지 못 한느 외판원 순회 문제인가요?

A Journey to Greece 문제 풀어보려고 했는데, N의 수가 커서 막혔네요 ㅠㅠ

완전 탐색으로는 절대 못 풀 것 같은데..

참고 블로그 : https://hsp1116.tistory.com/40


jh05013   4년 전

외판원 순회의 N은 저 문제의 N이 아니라 새로운 그래프의 정점 개수입니다.

park780172   4년 전

아 감사합니다! 시간복잡도 DP와 완전탐색 반대로 썼네요... 댓글 감사합니다. N의 뜻을 몰랐습니다.

park780172   4년 전

아아 그래서 '그래프 재구성'이라는 말씀을 하신거군요.. 감사합니다!

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