해리의 데브로그

SWEA 1247 - 최적 경로

03 Aug 2019 | Algorithm SWEA

문제

  • SWEA 1247 - 최적 경로
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

  • 백트레킹 문제인데, 회사 & 집 거리를 추가로 고려해줘야는 문제이다.
  • 추가로 시간 단축을 위해 프루닝 조건도 넣어주었다.
  • 거리를 계산하는 변수인 sub_result를 사용하여 이전 재귀로 돌아갈 때 기존 값을 빼주는 방식으로도 코드를 작성할 수도 있으며, 혹은 간단하게, 누적 값을 인자로 넘겨서도 풀 수 있다.
def DFS(x, y):
    global result, sub_result

    if sub_result > result:
        return

    if 0 not in visited:
        sub_result += abs(x - Home_x) + abs(y - Home_y)
        if result > sub_result:
            result = sub_result
        sub_result -= abs(x - Home_x) + abs(y - Home_y)
        return


    for i in range(N):
        x1 = Clients[i][0]
        y1 = Clients[i][1]
        if not visited[i]:
            visited[i] = 1
            sub_result += abs(x-x1) + abs(y-y1)
            DFS(x1, y1)
            visited[i] = 0
            sub_result -= abs(x-x1) + abs(y-y1)


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = list(map(int, input().split()))
    Office_x, Office_y = Data[0], Data[1]
    Home_x, Home_y = Data[2], Data[3]
    # print(Data)

    Clients = []
    for i in range(2, N+2):
        x = Data[i*2]
        y = Data[i*2+1]
        Clients.append([x,y])

    print(Clients)

    visited = [0]*N
    sub_result = 0
    result = 987654321
    DFS(Office_x, Office_y)
    print('#%d %d'%(tc, result))

def DFS(x, y, cnt):
    global result

    if cnt > result:
        return

    if 0 not in visited:
        cnt += abs(x - Home_x) + abs(y - Home_y)
        if result > cnt:
            result = cnt
        return


    for i in range(N):
        x1 = Clients[i][0]
        y1 = Clients[i][1]
        if not visited[i]:
            visited[i] = 1
            temp = abs(x-x1) + abs(y-y1)
            DFS(x1, y1, cnt+temp)
            visited[i] = 0


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = list(map(int, input().split()))
    Office_x, Office_y = Data[0], Data[1]
    Home_x, Home_y = Data[2], Data[3]
    # print(Data)

    Clients = []
    for i in range(2, N+2):
        x = Data[i*2]
        y = Data[i*2+1]
        Clients.append([x,y])

    visited = [0]*N
    # cnt = 0
    result = 987654321
    DFS(Office_x, Office_y, 0)
    print('#%d %d'%(tc, result))

Related Posts

Comments