[삼성 SW Expert Academy] 1247. 최적 경로

문제

1247 [S/W 문제해결 응용] 3일차 - 최적 경로

풀이

1. 초기접근

• 문제조건 해석

  • N <= 10 으로, 매우작음.

  • 모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.

    => 모든 경우를 다 해보는 방법을 고려해보자.

  • 가장 직관적인 방법은, 각 포인트의 거리들을 미리 구하고, 순열로 생성하며 모든 경우의 수를 탐색하는 것이다.

• 알고리즘

  • 각 포인트들의 좌표를 가지고 만들 수 있는 모든 순열을 탐색해보며, 각 경우에서의 거리를 구해 최소 거리를 갱신.
  • 순열을 만드는 방법은 파이썬 내장 함수인, itertools.permutations() 로 손쉽게 구현

• 코드

import itertools

t = int(input())
for tc in range(1, t+1):
    n = int(input())
    l = list(map(int, input().split()))

    # 회사, 집, 그리고 각 포인트들을 구분하여, 각 좌표를 튜플로, 저장.
    company = (l[0], l[1])
    home = (l[2], l[3])
    points_sliced = l[4:]
    points = []
    for i in range(0, len(points_sliced), 2):
        points.append((points_sliced[i], points_sliced[i+1]))

    # 포인트들의 경로를 순열을 이용하여 모드 경우의 수를 탐색.
    min_distance = float('inf')
    for i in itertools.permutations(points):

        # 각 경로 시작과 끝에 뒤에 회사와 집의 좌표를 넣어줌.
        path = [company, *list(i), home]
        # path 는 예를 들어 아래와 같은 꼴임.
        # path = [(0, 0), (70, 70), (30, 30), (10, 10), (90, 90), (50, 50), (100, 100)] 

        # 각 경로에서의 걸리는 거리를 구함.
        distance = 0
        for idx in range(0, len(path)-1):
            #distance += sum([abs(b-a) for a, b in zip(path[idx-1], path[idx])])
            distance += abs(path[idx][0] - path[idx+1][0]) + abs(path[idx][1]-path[idx+1][1])

        min_distance = distance if distance < min_distance else min_distance
    print("#%d %d" %(tc, min_distance))

2. 유의할 점

• for i in itertools.permutations(points) 에서 i 는 튜플임.
  즉, i = ( (0, 0), (70, 70), (30, 30), (10, 10), (90, 90), (50, 50), (100, 100) ) 와 같은 꼴임.
  • 따라서, *list(i) 와 같이 list로 만든 뒤, unpacking 해줘야 함.
• 주석처리한 distance += sum([abs(b-a) for a, b in zip(path[idx-1], path[idx])]) 부분과 같이 써도 되지만, 좀 더 직관적인 코드로 적고자, distance += abs(path[idx][0] - path[idx+1][0]) + abs(path[idx][1]-path[idx+1][1]) 을 사용.
• 이 코드는 별로 파이썬스럽지 않아서 조금 아쉬움…

참고

Youth-tory 유스토리 님 블로그.