난이도 : D5
문제번호 : 1267
문제 주소 및 출처입니다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
목차
1. 문제 설명
2. 문제 해석
3. 소스 코드
1. 문제 설명
삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다. 회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100) 두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다. 여기서 |x|는 x의 절대값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다. 회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다. 회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때, 회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라. 여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다. 이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다. 여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다. 모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다. 고객의 수 N은 2≤N≤10 이다. 그리고 회사의 좌표, 집의 좌표를 포함한 모든 N+2개의 좌표는 서로 다른 위치에 있으며 좌표의 값은 0이상 100 이하의 정수로 이루어진다. |
입력
가장 첫줄은 전체 테스트케이스의 수이다. |
출력
총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다. |
예시
입력 | 출력 |
10 5 0 0 100 100 70 40 30 10 10 5 90 70 50 20 6 88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14 10 39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36 ... |
#1 200 #2 304 #3 366 ... |
2. 문제풀이
전형적인 TSP문제이다. |
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
|
#D5 1247 최적경로
def dfs(index, lastX, lastY, distance):
global min_count
if min_count < distance:
return
#모든경로 탐색이 완료되었다면
if index == length:
#거리를 계산한다.
distance += abs(lastX - home_position[0]) + abs(lastY - home_position[1])
#제일짧은거리 리턴
min_count = min(distance, min_count)
return
#경로를 하나씩 추가한다.
for i in range(length):
#탐색하지 않았다면
if check[i]:
#사용했다고 체크하기
check[i] = False
#재귀하기
temp = distance + abs(lastX - position_list[i][0]) + abs(lastY - position_list[i][1])
dfs(index+1, position_list[i][0], position_list[i][1], temp)
#돌아오면 사용체크 해제
check[i] = True
T = int(input())
for t in range(1, T+1):
#위치 입력받기
length = int(input())
#좌표값을 받는 임시리스트
temp_list = list(map(int, input().split()))
#각각의 위치를 저장하는 리스트
position_list = []
#방문여부 체크리스트
check = [True for _ in range(length)]
#최소값 카운트용
min_count = 1000
company_position = []
home_position = []
#각사람의 위치더하기
for i in range(0, len(temp_list), 2):
position_list.append([temp_list[i], temp_list[i+1]])
company_position = position_list.pop(0)
home_position = position_list.pop(0)
#경로찾기 시작
dfs(0, company_position[0], company_position[1], 0)
print("#{} {}".format(t, min_count))
|
'코딩테스트 > SWExpertAcademy' 카테고리의 다른 글
금속막대 Python(SW Expert Academy, SWEA) (0) | 2020.06.04 |
---|---|
공통조상(SW Expert Academy, SWEA) (0) | 2020.06.03 |
작업순서 Python(SW Expert Academy, SWEA) (0) | 2020.06.01 |
상원이의 생일파티 Python(SW Expert Academy, SWEA) (0) | 2020.05.31 |
장훈이의 높은 선반(SW Expert Academy, SWEA) (1) | 2020.05.30 |
댓글