sw expert academy 1242번 최적 경로 자바(java) 풀이
문제정리
- 회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾는다.
- 모든 좌표는 다르게 주어진다.
- 문제에 쓰여있듯이 모든 경우를 따져주면 된다.
문제풀이
- 완전 탐색
고객의 수가 최대 10명이므로 최대 10!을 계산하면 됩니다.
제한시간은 tc 모두 합쳐서 20초입니다(자바의 경우). 그러므로 완탐으로 충분히 가능합니다.
0. 좌표를 편하게 입력받기 위해 x,y 좌표를 저장할 Pos 클래스를 선언합니다.
- 입력을 받아 집, 회사 좌표를 따로 저장합니다.
- 고객들의 좌표를 배열에 저장합니다.
- dfs를 통해 고객들의 좌표의 나열 가능한 모든 경우를 구합니다( 순열 )
- 이동한 거리를 재귀를 통해 넘길때 현재 선택한 집과 이전 집의 거리를 더해서 넘깁니다.
- N개의 집을 모두 선택해 나열했다면 마지막으로 선택한 집과 회사와의 거리를 더해주고 min 보다 작으면 갱신해줍니다.
- DP 기법 이용(메모이제이션)
TSP(Traveling Salesman Problem), 비트 마스킹 방법을 이용하여 풀 수 있습니다.
TSP는 NP문제로 유명한 문제입니다. 출발지에서 모든 정점을 한 번씩 거쳐서 출발지로 돌아오는 최소 비용을 구하는 문제입니다.
오른쪽에서 부터 i번째 수가 1이면 i번째 도시를 방문했음을, 0이면 방문하지 않았음을 의미합니다.
예를 들어 5개의 도시가 있고 1,2,3번 도시를 방문했다면 00111로 표현합니다.
이미 방문한 도시들과 현재 위치한 도시가 같을 때, 나머지 도시들을 방문하고 출발 도시로 돌아가는 최소 비용은 같습니다.
1-2-3-4-5 와 2-1-3-4-5 두 가지 방법으로 가능하다면 3번 도시 뒤의 점들은 같기 때문에 한 번만 계산할 수 있습니다.
dp[i][j] : 이미 방문한 도시들의 집합이 i이고 현재 있는 도시가 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용.
0. 재귀로 구현합니다.
1. 방문 했음을 비트마스킹으로 체크 합니다. (visit |= (1 << now))
2. 모든 집들을 방문 했다면 마지막 방문지에서 집까지의 거리를 반환합니다.
3. 이미 계산한 값이 있다면 그 값을 반환합니다.
4. for문을 돌며 지금 방문하려는 점이 아니고(now가 아니고) 방문한 점이 아닌 경우 방문하여 거리를 누적하여 구합니다.
최적경로 자바 소스코드
- dfs, 완전 탐색
주석을 달아 두었습니다.
메모리: 20032kb
실행시간: 1286ms
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Pos {
int x;
int y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
class Solution {
static int N;
static Pos home;
static Pos office;
static Pos[] customer;
static int min;
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
N = Integer.parseInt(br.readLine());
// 회사, 집, N명의 고객의 좌표
String[] temp = br.readLine().split(" ");
home = new Pos(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
office = new Pos(Integer.parseInt(temp[2]), Integer.parseInt(temp[3]));
customer = new Pos[N];
// 고객의 집의 좌표 저장
int idx = 0;
for(int i=4; i<4+N*2; i+=2)
customer[idx++] = new Pos(Integer.parseInt(temp[i]), Integer.parseInt(temp[i+1]));
min = Integer.MAX_VALUE;
visited = new boolean[N];
// dfs를 통해 모든 경우 탐색(순열)
dfs(0,home.x, home.y,0);
System.out.println("#" + test + " " + min);
}
br.close();
}
public static void dfs(int k, int x, int y, int dist){
if(k == N){
// 마지막 방문한 집과 회사의 거리를 더해준다.
dist += getDistance(x, y, office.x, office.y);
// min 값 보다 작을 경우 갱신
min = min > dist ? dist : min;
return;
}
for(int i=0; i<N; i++){
if(!visited[i]){
visited[i] = true;
// 선택한 고객의 집의 customer[i].x, customer[i].y 좌표를 넘긴다. => 넘어가서 이전 집의 좌표가 된다.
// 이전 집의 x,y좌표와 현재 선택한 집의 cusromer[i].x, customer[i].y 좌표와의 거리를 계산하여 넘긴다.
dfs(k+1, customer[i].x, customer[i].y, dist + getDistance(x, y, customer[i].x, customer[i].y));
visited[i] = false;
}
}
}
public static int getDistance(int x, int y, int x2, int y2){
return Math.abs(x-x2) + Math.abs(y-y2);
}
}
- DP, 메모이제이션
메모리: 25236 kb
실행시간: 112 ms