안녕하세요. BlockDMask 입니다.
오늘의 문제 풀어보겠습니다.
0. 제목
백준 10971 외판원 순회 2
BOJ 10971 외판원 순회 2
1. 문제 설명
외판원 순회 문제는 영어로 Traveling Salesman Problem(TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다.
(길이 없을 수도 있다.)
이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.단, 한번 갔던 도시로는 다시 갈 수 없다.
(맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)
이런 여행 경로는 여러가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.각 도시간에 이동하는데 드는 비용은 행렬 W[i][j] 형태로 주어진다.
W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.
비용은 대칭적이지 않다.
즉, W[i][j]는 W[j][i]와 다를 수 있다.모든 도시간의 비용은 양의 정수이다.
W[i][i]는 항상 0이다.경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며, 이럴 경우 W[i][j]=0이라고 한다.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원 순회 여행 경로를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 수 N이 주어진다. (2<=N<=10)
다음 N개의 줄에는 비용 행렬이 주어진다.
각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다.
W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.출력
첫째 줄에 외판원 순회에 필요한 최소 비용을 출력한다.
2. 풀이 과정
각각의 도시에서 시작해서 전체 탐색을 하는 방식으로 깊이 우선 탐색(DFS)을 통해서 구했습니다.
한도시 a에서 시작해서 다른 도시 b로 가게 되면 [a,b]를 들르고 도시를 방문했다는 표시를 배열 check에 하게 됩니다.
도시를 가는 길의 비용(가중치)를 계속 변수 sum 에 더하면서 탐색을 진행 합니다.
재귀를 통한 탐색을 진행하다가
종료조건을 만나게 되면 return 하게 됩니다.
여기서 종료 조건은 모든 도시를 방문했고, 다시 처음의 도시로 돌아 온 경우를 말합니다.
** 전체 탐색이라 했지만, 경로의 최소 값을 구하는 것 이므로 도시의 비용인 sum이 최소값인 m 보다 큰 경우는 더이상 탐색을 진행하지 않았습니다.
아래 if(sum<=m) 부분의 조건문을 사용하지 않으면 시간이 1200MS 대로 엄청나게 뛰게 됩니다.
3. 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | //https://www.acmicpc.net/problem/10971 //BOJ_10971_TravelingSalesmanProblem #include<iostream> #include<cstdio> using namespace std; int arr[11][11]; //map. int check[11]; //도시를 방문 했는지 check int n; //n. int m = 987654321; //순회의 최소 비용 void input(){ scanf("%d", &n); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ scanf("%d", &arr[i][j]); } } } void dfs(int start, int y, int sum, int cnt){ //모든 도시를 들렀고(cnt==n) && 다시 스타트 도시로 온 경우(start==y) if(cnt == n && start == y){ if(m > sum) m = sum; return; } for(int x=0; x<n; x++){ if(arr[y][x] == 0) continue; //연결 되지 않은 경우(자기자신포함) //방문 하지 않고 y,x가 0보다 큰 경우 if(!check[y] && arr[y][x] >0) { check[y] = true; //방문 체크 sum+=arr[y][x]; if(sum <= m){ //sum이 m 보다 작은 경우만 탐색 진행 //[1,2]이었으면 [2,-]로 보내줌. dfs(start, x, sum, cnt+1); } //방문한 기록과 합 초기화 check[y] = false; sum-=arr[y][x]; } } } void solution(){ for(int y=0; y<n; y++){ //각각의 점(도시)에서 시작하는 경우 dfs(y, y, 0, 0); } } void output(){ printf("%d", m); } int main(void){ input(); solution(); output(); return 0; } | cs |
4. 인증
if 조건 있을때.
if 조건문 없이 전체 탐색을 그대로 진행했을때.
감사합니다.
'<알고리즘 문제풀이&연습> > [C++] 백준, 프로그래머스 등등' 카테고리의 다른 글
[백준 2447] 별찍기10 (1) | 2017.11.22 |
---|---|
[백준 2446] 별찍기9 (0) | 2017.11.21 |
[백준 10820] 문자열 분석 (0) | 2017.11.21 |
[백준 2445] 별찍기8 (0) | 2017.11.20 |
[백준 2444] 별찍기7 (0) | 2017.11.15 |
[백준 1120] 문자열 (0) | 2017.11.14 |
[백준 2443] 별찍기6 (0) | 2017.11.14 |
[백준 11721] 열 개씩 끊어 출력하기 (0) | 2017.11.14 |