[SWEA] 1247. 최적 경로/Python - D5

❓문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&problemLevel=5&contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=5&pageSize=10&pageIndex=1

SW Expert Academy

✍🏻풀이

예제는 회사, 집, N명의 고객 좌표를 순서대로 준다. 그러므로 우선 먼저 회사와 집의 좌표를 먼저 구해 시작점과 끝점을 찾는다.

시작점은 회사로 하여 회사와 가까운 고객을 가지치기로 하면서 찾는다. 그리고 이후 각 고객 간의 가까운 곳을 가지치기하면서 찾고 마지막에 마지막으로 방문한 고객과 집까지의 거리를 계산하여 최소 거리를 구하면 된다.

💻코드

def backtracking(visited, pre, cnt, dist):
    global res

    if cnt == N:
        r = abs(home[0]-clients[pre][0]) + abs(home[1]-clients[pre][1])
        res = min(res, dist+r)
        return

    for i in range(N):
        if not visited[i]:
            if cnt == 0:
                r = abs(company[0]-clients[i][0]) + abs(company[1]-clients[i][1])
                visited[i] = True
                backtracking(visited, i, cnt+1, dist+r)
                visited[i] = False
            else:
                visited[i] = True
                r = abs(clients[pre][0]-clients[i][0]) + abs(clients[pre][1]-clients[i][1])
                backtracking(visited, i, cnt+1, dist+r)
                visited[i] = False


test_case = int(input())
for tc in range(1, test_case+1):
    res = 1e9
    N = int(input()) # 고객 수
    visited = [False] * N

    # 회사, 집, 고객
    coords = list(map(int, input().split()))

    company = coords[:2]
    home = coords[2:4]
    clients = []
    for i in range(4, len(coords), 2):
        clients.append((coords[i], coords[i + 1]))

    backtracking(visited, -1, 0, 0)

    print(f"#{tc} {res}")

📍후기

처음에는 최소신장트리인가 생각했는데 그러면 일일히 가중치 계산해야 하니까 시간이 오래 걸릴 것 같다고 느껴졌다. 다른 방법은 뭐가 있을까하고 밑에 댓글보니까 DFS라고 해서 이걸 DFS로 어떻게 하지 엄청 고민했다..코테 공부를 너무 오랜만에 해서 그런지 어렵다...

그리고 역시 파이썬 메모리 많이 차지한다...게다가 삼성은 PyPy로 해서 메모리를 더 많이 차지한다...