[SWEA] D5. 최적 경로

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYUu1hG6O44DFARs&contestProbId=AV15OZ4qAPICFAYD&probBoxId=AYUyLcVaojsDFARs&type=PROBLEM&problemBoxTitle=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+Track+%28%EB%82%9C%EC%9D%B4%EB%8F%84+%EC%83%81%29&problemBoxCnt=6 

SW Expert Academy

 

 

1. 해결방법

가지치기를 하면 좋지만 아직 실력이 부족해서 모든 경우를 탐색하는 dfs로 해결하였다.

1. 거쳐가야 하는 집을 targets이라는 리스트로 만들어서 따로 처리.
2. dfs를 돌면서 temp에 dis와 해당 집 거리를 계산하여서 dis 거리 저장 변수에 갱신
3. depth가 N일 때, 종료 후 거쳐간 마지막 집에서 본인 집까지의 거리를 추가한 후 리턴

 

 

2. 정답코드

# T = int(input())
T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    numbers = list(map(int, input().split()))
    chk = [False] * N

    min_v = 1e9
    def dfs(depth, company, dis):
        global min_v, home


        if depth == N:
            dis += abs(home[0] - company[0]) + abs(home[1] - company[1])
            min_v = min(min_v, dis)
            return

        for i in range(N):
            if chk[i] == False:
                chk[i] = True
                temp = dis + abs(company[0] - targets[i][0]) + abs(company[1] - targets[i][1])
                dfs(depth + 1, (targets[i][0], targets[i][1]), temp)
                chk[i] = False

    targets = []
    for i in range(4, len(numbers), 2):
        targets.append((numbers[i], numbers[i + 1]))

    company = (numbers.pop(0), numbers.pop(0))
    home = (numbers.pop(0), numbers.pop(0))

    dfs(0, company, 0)


    print(f'#{test_case} {min_v}')