최적경로 Python(SW Expert Academy, SWEA)

난이도 : D5

문제번호 : 1267

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE

SW Expert Academy

---

목차

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 이하의 정수로 이루어진다.

입력

가장 첫줄은 전체 테스트케이스의 수이다. 이후, 두 줄에 테스트 케이스 하나씩이 차례로 주어진다. 각 테스트 케이스의 첫째 줄에는 고객의 수 N이 주어진다. 둘째 줄에는 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다. 좌표는 (x,y)쌍으로 구성되는데 입력에서는 x와 y가 공백으로 구분되어 제공된다.

출력

총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 최단 경로의 이동거리를 기록한다. 여기서 x는 테스트 케이스의 번호다.

예시

입력	출력
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. 소스코드

#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))