⭐️
def dfs(startX, startY, distance):
global clients, visited, answer
clientsNotFinished = False
for cidx in range(len(clients)):
if not visited[cidx]:
clientsNotFinished = True
targetX, targetY = clients[cidx][0], clients[cidx][1]
dist = abs(targetX - startX) + abs(targetY - startY)
visited[cidx] = True
dfs(targetX, targetY, distance + dist)
visited[cidx] = False
# 집으로
if not clientsNotFinished:
distHome = abs(home[0] - startX) + abs(home[1] - startY)
answer = min(answer, distance + distHome)
T = int(input())
for test_case in range(1, T + 1):
answer = float('inf')
N = int(input())
info = list(map(int, input().split()))
company, home = [info[0], info[1]], [info[2], info[3]]
visited = [False for i in range(10)]
clients = []
for i in range(4, 4+2*N, 2):
clients.append([info[i], info[i+1]])
# 고객 방문
dfs(company[0], company[1], 0)
print("#" + str(test_case), answer)
처음에 문제를 풀 때 접근 로직을 잘못 설계했다. 문제에서 다음과 같이 설명하고 있다.
여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.
이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.
여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.
모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.
따라서 회사 -> 모든 클라이언트(n <= 10)를 방문 -> 집 까지의 과정이 항상 그때 상황에서 최적의 경로를 선택하면 그 합이 곧 가장 짧은 이동거리가 된다고 판단했었다.
그러나 이 생각은 잘못된 판단이었다. 각각에서의 최소 경로의 합이 최소가 된다는 보장을 할 수가 없다. 따라서 이 문제는 모든 경우를 살펴보는 것이 맞다.
두번째 도전은 클라이언트의 순서를 조합해 모든 경우를 계산한 뒤, 그 중 가장 작은 값을 뽑아내자는 생각이었다. 그러나 이 경우에 Memory Limit Exceed 에러가 났다. 구현한 permutations 메서드가 메모리를 많이 잡아먹는 모양이었다. 어쩔 수 없이 다른 방법을 생각해야 했다.
마지막 도전은 dfs 백트래킹으로 접근하는 방법이었다. 클라이언트 방문을 배열로 두고 백트래킹을 사용하면서 모든 방법을 확인했다. 이렇게 해서 문제없이 통과를 할 수 있게 되었다.
왜 처음부터
백트래킹을 생각해 내지 못했나
우선 첫번째 생각했던 각각에서의 최적 경로의 합 => 전체적으로 최적 경로 의 발상은 잘못된 생각이다. 이것이 참이라는 것을 증명을 할 수가 없다.
두번째로 생각했던 순열 메서드 구현은 잘 생각해봐야 한다. 문제 통과 시간을 여유있게 준다고 해서 메모리도 여유있게 준다고 하진 않았다.
순열은 메모리를 많이 잡아먹기 때문에 쓰기 전에 가능할지 잘 생각해 봐야 한다.
이제 이런 류의 문제는 웬만하면 백트래킹으로 접근해보자. 백트래킹도 깊이가 깊어지면 문제가 될 수 있지만 모든 고객을 거쳐야 하고, 전체적으로 최적 경로의 거리를 계산해야 하기 때문에 모든 경우를 다보긴 해야 한다. 따라서 이 문제의 경우 백트래킹으로 푸는게 맞다.
문제 출처:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD
