문제 정보
https://www.acmicpc.net/problem/10971
문제
외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.
접근방법
swea 전자카트와 유사한 문제
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do
TSP 라는 아주 유명한 문제
조합을 만들고 배열을 순회하면서 최소값을 찾아내면 해결할 수 있다.
대신 지금 푼 코드로 제출하면 외판원 순회 1은 통과 못한다
16! = 조가 넘음
1차 풀이(오답)
def find_travel(dep):
global minV
S = 0
if dep == n:
way = nums + [nums[0]]
# print(way)
for i in range(0, len(way) - 1):
S += zido[way[i] - 1][way[i + 1] - 1]
if S > minV:
return
if minV > S:
minV = S
else:
for i in range(dep, n):
nums[dep], nums[i] = nums[i], nums[dep]
find_travel(dep + 1)
nums[dep], nums[i] = nums[i], nums[dep]
n = int(input())
zido = [list(map(int, input().split())) for _ in range(n)]
nums = [i + 1 for i in range(n)]
minV = 987654321
find_travel(0)
print(minV)
else 에서 조합을 만어주고 만든 조합으로 외판원을 이동시켜 준다.
여행을 마치고 처음 출발한 도시로 되돌아와야 하기 때문에 조합의 가장 첫번째 숫자를 추가해준다.
이동하며 소모한 비용을 더해주고 최소값을 갱신해 준다.
하지만 현재 최소값보다 이동하며 소모한 비용이 더 크다면 어차피 minV 를 갱신할 수 없기 때문에
더이상 움직이지 않고 return
하지만 이동하지 못하는 경우에 대해서 체크해주지 못해서 fail
2차 풀이(정답)
def find_travel(dep):
global minV
S = 0
if dep == n:
way = nums + [nums[0]]
# print(way)
for i in range(len(way) - 1):
S += zido[way[i] - 1][way[i + 1] - 1]
if zido[way[i] - 1][way[i + 1] - 1] == 0:
return
if S > minV:
return
if minV > S:
minV = S
else:
for i in range(dep, n):
nums[dep], nums[i] = nums[i], nums[dep]
find_travel(dep + 1)
nums[dep], nums[i] = nums[i], nums[dep]
n = int(input())
zido = [list(map(int, input().split())) for _ in range(n)]
nums = [i + 1 for i in range(n)]
minV = 987654321
find_travel(1)
print(minV)
위의 코드와 동일하지만 이동하려는 위치가 0 이면
이동하지 못하기 때문에 return 해준다.
또 조합은 순서만 다를 뿐 어디에서 시작하든지 똑같은 경로를 지나간다.
따라서 굳이 0번부터 시작해서 모든 조합을 이용할 필요가 없다.
시작하는 위치를 1로 고정시켜주고 마지막에 1을 추가해줘도 동일하게 해결 가능하다.
느낀점
전자카트랑 유사한 문제라고 문제도 안읽고 대충풀었더니 개판났다ㅋㅋㅋ
문제를 잘 읽자 제발
조합을 만드는 방법 에 대해서 대강 알거같기도 하고 모를거같기도 하다.
N = 4
arr = [i for i in range(1, N + 1)]
def perm(k):
if k == N:
print(arr)
else:
for i in range(k, N):
arr[k], arr[i] = arr[i], arr[k]
perm(k + 1)
arr[k], arr[i] = arr[i], arr[k]
perm(0)
n = 4 arr = [1,2,3,4] k = 깊이
일때 arr의 k 와 i 에 해당하는 위치의 숫자를 바꾼다.
함수를 재귀호출 해서 깊이와 n 이 같아졌을 때 변경한 arr 를 출력한다.
출력 후 자리가 변경된 arr를 다시 원상복구 시켜야 조합이 순서대로 생성된다.
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 5014 스타트 링크 (파이썬) (0) | 2022.10.13 |
---|---|
백준 8979 올림픽 (파이썬) (0) | 2022.09.26 |
백준 1182 부분수열의 합 (파이썬) (부분 집합 생성 방법) (0) | 2022.09.24 |
백준 1967 트리의 지름 (파이썬) (0) | 2022.09.21 |
백준 1181 단어 정렬 (파이썬) (0) | 2022.09.20 |