TSP

문제 링크https://www.acmicpc.net/problem/14590 문제고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.  순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하..

문제 링크https://www.acmicpc.net/problem/24519  문제외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Problem (BTSP) 문제를 살펴보자.정점의 개수가 N개, 비용이 있는 간선이 M개인 방향 그래프가 주어진다. 어느 한 정점에서 출발해, 출발한 정점을 제외한 N − 1개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다. 이러한 순회는 여러 가지가 있을 수 있는데, 정점 간 이동 비용의 최댓값을 최소화하려고 한다.그래프..

문제 링크https://www.acmicpc.net/problem/30975  문제진주 나들이를 온 보선이는 경상국립대 정문 쪽 연못 산책길을 걷다가 울고 있는 동기 원우를 발견했다. 반가움보다 안쓰러움이 앞선 보선이는 원우한테 다가가서 울고 있는 이유를 물어봤다. 원우는 울면서 "교수님께서 경상국립대에서 출발해 경상국립대 주변에 있는 모든 동네에 가서 하늘 사진을 찍은 다음, 다시 경상국립대로 돌아오라는 심부름을 시키셨는데 거절을 못했어. 그런데 어떻게 심부름을 끝내야 할지 모르겠어."라고 대답했다. 약간 모자라지만 착한 원우를 위해 보선이가 대신 심부름을 맡기로 했다.경상국립대 주변에 있는 동네는 총 N개이며, 각 동네는 1번부터 차례대로 번호가 부여되어 있다. 또한, 보선이는 편의상 경상국립대가 N..

문제 링크https://www.acmicpc.net/problem/16991 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 모든 도시 사이에는 길이 있다. 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있..

문제 링크https://www.acmicpc.net/problem/2098 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러..