링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD

풀이

DSF를 활용해 회사 → ...→ 집 으로 가는 모든 경우의 수를 따진후 비용이 가장 적은 결과를 출력

코드

cases = int(input())
def DFS(x,y,cost,check):
    global answer
		#마지막 방문지인 집 이외의 모든 노드를 방문한 경우 
    if sum(check)==len(check)-1:
				#집과 현재 위치 사이에 거리를 구해 cost에 더해줌
        cost = cost + getCost(x,y,nodeInfo[1][0],nodeInfo[1][1])
        #print(x,y,cost,check)
        answer = min(answer,cost)
		#모든 경우의 수를 조사하기 위해 포문을 통해 제귀함수 호출
    for i in range(2,len(nodeInfo)):
        if check[i]==0:
            nx = nodeInfo[i][0]
            ny = nodeInfo[i][1]
            check[i]=1
            DFS(nx,ny,cost+getCost(x,y,nx,ny),check)
            check[i]=0
#각 포인트 간의 거리를 구하는 함수
def getCost(x,y,dx,dy):
    return abs(x-dx)+abs(y-dy)

for tcase in range(1,cases+1):
    n = int(input())
    answer = 987654321
    info = list(map(int,input().split()))
    nodeInfo = []
    check = [0 for _ in range(len(info)//2)]
		//시작점 방문 표시
    check[0]=1
    for i in range(0,len(info),2):
        nodeInfo.append([info[i],info[i+1]])
    

    DFS(info[0],info[1],0,check)
    print(f"#{tcase} {answer}")