문제
https://swexpertacademy.com/main/code/problem/problemDetail.do
문제 설명
- 회사 좌표 S에서 N명의 고객의 좌표를 모두 방문한 후, 집 좌표 E로 이동하려고 한다.
- 두 위치 (x1,y1), (x2,y2)의 거리는 |x1-x2| + |y1-y2|으로 계산된다.
- 각 좌표는 모두 다르다.
- S에서 출발해서 N명의 고객을 모두 방문한 후 E로 이동하는 경로중 최단 경로를 구해야 한다.
풀이
이 문제의 N은 10이다.
따라서 모든 경우의 수를 탐색해보면, 10 * 9 * 8 * 7 * 6 ... * 2 * 1 = 3,628,800개이다.
즉, 완전탐색으로 모든 경우의 수를 탐색해도 문제를 풀이할 수 있다.
시작 좌표부터 하나씩 좌표를 선택하고, 방문 처리하며 백트래킹하는 방식으로 문제를 풀이했다.
총 $3*10^6$ 정도의 연산을 진행하기 때문에 시간이 꽤 오래 걸렸다.
현재 구조에서는 모든 경우의 수를 전부 탐색해야 결과를 도출할 수 있기 때문에, 중간에 프루닝할 수 있는 방법을 생각했다.
모든 경우의 수를 탐색하다 보면 최단거리가 초반에 나올 수도 있고, 가장 마지막에 나올 수도 있다.
그렇기 때문에 기본적으로 모든 경우의 수를 탐색해야 하지만, 매 좌표에 들어갔을 때 현재 가지고 있는 최단 거리보다 현재까지 갱신 중인 거리가 더 크다면 더 이상 탐색할 필요가 없다고 판단했다.
즉, 매 재귀마다 현재 최단 거리 < 현재 갱신 중인 거리라면 해당 재귀는 더 이상 진행하지 않도록 return했다.
실제로 코드를 돌려보니 훨씬 더 빠르게 동작하는 것을 확인할 수 있었다.
예전에 백준에서도 유사한 문제를 풀었던 적이 있다. 주어진 2차원 배열 안에서 겹치지 않는 사각형을 만드는 문제였던 걸로 기억한다.
그 문제에서도 같은 방식으로 프루닝을 진행하지 않으면 시간 초과가 발생했다.
이 문제에서도 거의 동일한 문제가 발생했고, 그때 풀었던 기억이 나서 프루닝을 통해 시간을 단축할 수 있었다.
백트래킹 최단거리 탐색 문제에서 꼭 필요한 테크닉이라고 생각하고 기억해두면 좋을 것 같다.
코드
INF = int(1e10)
def cal_dist(p1,p2):
return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def solve(idx, depth, dist):
global res
if depth == N:
res = min(dist + cal_dist(arr[idx],[ey,ex]), res)
return
if dist > res:
return
for i in range(N):
if visited[i]:
continue
cur_dist = cal_dist(arr[idx], arr[i])
visited[i] = 1
dist += cur_dist
solve(i, depth + 1, dist)
visited[i] = 0
dist -= cur_dist
for tc in range(1,int(input())+1):
N = int(input())
arr = []
tmp = list(map(int,input().split()))
sy,sx,ey,ex = tmp[0],tmp[1],tmp[2],tmp[3]
for i in range(1,N+1):
arr.append([tmp[(i+1)*2],tmp[(i+1)*2+1]])
arr.sort(key = lambda x: (x[0], x[1]))
res = INF
visited = [0 for _ in range(N)]
for i in range(N):
dist = cal_dist([sy,sx],arr[i])
visited[i] = 1
solve(i,1, dist)
visited[i] = 0
print(f'#{tc} {res}')시간복잡도
- 최악의 경우 $N = 10$이다. 백트래킹으로 모든 경우의 수를 탐색하면 $10! = 3628800, O(3*10^6)$정도의 시간복잡도를 가진다.