[SW] 1247. 최적 경로

1247. 최적 경로

SW Expert Academy

 

• 내 풀이 - fail
  • permutations 로 순열 불러오는 과정에서 메모리초과 발생
  • DFS로 풀어야함

from itertools import permutations
T=int(input())
for test_case in range(1,T+1):
    n=int(input())
    ls=list(map(int,input().split()))
  
    for i in range(len(ls)):
        if i%2==0:
            x=ls.pop(0)
        else:
            y=ls.pop(0)
            if i==1:
                start=(x,y)
            elif i==3:
                end=(x,y)
            else:
                ls.append((x,y))

    answer=1e9
    combi=list(permutations(range(n),n))
    success=[1e9]*(n)
    
    for com in combi:
        result, flag=0,0
        dx,dy=start
        cnt=-1

        for c in list(com):
            cnt+=1
            cx,cy=ls[c]
            result+=abs(cx-dx)+abs(cy-dy)
            if result>answer:
                flag=1
                break
            dx,dy=cx,cy
        if flag:
            continue
          
        ex,ey=end
        result+=abs(ex-dx)+abs(ey-dy)
        answer=min(answer,result)
            
    print("#{} {}".format(test_case, answer))

 

• 다른 사람 풀이
  • 주의) temp_distance 대신 distance+= abs()~~ 하면 바뀐 distance 값으로재귀를돌기 때문에 에러

def dfs(depth,lastX,lastY,distance):
    global result
  
    #기존 최소거리보다 거리가 커지면 pass
    if result< distance:
        return
      
    if depth==n:
        distance+=abs(homeX-lastX)+abs(homeY-lastY)
        result=min(result,distance)
        return

    #순열전체 돌기
    for i in range(n):
        if not visited[i]:
            visited[i]=True
            #모든 값들이 다 1번이 되어보기 때문에
            tmp_distance=distance+ abs(customer[i][0]-lastX)+ abs(customer[i][1]- lastY)
            dfs(depth+1, customer[i][0], customer[i][1],tmp_distance)
            visited[i]=False

          
T=int(input())  
for test_case in range(1,T+1):
  
    n=int(input())
    result=1e9
    visited=[False for _ in range(n)]
    temp=list(map(int,input().split()))

    companyX=temp.pop(0)
    companyY=temp.pop(0)
    homeX=temp.pop(0)
    homeY=temp.pop(0)

    customer=[]
    for i in range(0,len(temp),2):
        customer.append([temp[i],temp[i+1]])
        
    dfs(0,companyX,companyY,0)

    print("#{} {}".format(test_case, result))