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

코드

## SWEA 1247
def dfs(node,dist):
    global result
    if dist > result:
        return

    if sum(visited) == len(visited) :
        tmp = abs(node_arry[node][0]-end[0])+abs(node_arry[node][1]-end[1])
        dist += tmp
        if dist < result :
            result = dist
        return

    for i in range(N):
        if visited[i] == 0 :
            visited[i] = 1
            tmp = abs(node_arry[node][0] - node_arry[i][0])+abs(node_arry[node][1] - node_arry[i][1])
            dist += tmp
            dfs(i,dist)
            dist -= tmp
            visited[i] = 0


T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arry = list( map(int, input().split()) )
    start = [arry[0],arry[1]]
    end = [arry[2], arry[3]]
    node_arry = []
    for i in range(4, len(arry), 2) :
        node_arry.append( [arry[i],arry[i+1]] )
    result = float("inf")


    for i in range(N):
        visited = [0] * N
        visited[i] = 1
        dist = abs(start[0]-node_arry[i][0])+abs(start[1] - node_arry[i][1])
        dfs(i,dist)

    print(f"#{test_case} {result}")

 

풀이

문제에서 완전탐색으로 풀라고 가이드를 줘서 DFS로 풀었다.