[SWEA/Java] 1247 : 최적경로

문제

 

 

 

 

풀이

 

김대리가 회사에서 출발해 N명의 고객의 집에 방문한 뒤에 집까지 도착할 때까지의 경로 중 최소인 값을 구해야하는 문제이다. 김대리 기준으로 가까운 고객의 집부터 방문한다고 해서 최종 답이 나오는 것은 아니므로 주의해야 한다.

N명 고객을 기준으로 순열을 만들어 모든 경우의 수를 따져본 뒤에 최종 답을 구해야 한다.

 

풀이 순서는 다음과 같다

1. N명의 고객을 기준으로해 N!개의 순열을 만들어 모든 경우를 따져본다
2. 정해진 순서를 바탕으로 고객의 집에 방문한다
3. 고객의 집에 방문할 때마다 거리를 count 해주고 김대리의 위치도 옮겨준다
4. 고객의 집에 모두 방문하고 나면 김대리 집까지의 최소 경로도 더해준다
5. 다음 순서로 경로를 구하기 위해 김대리의 위치를 처음 위치로 돌려놓는다
6. 모든 순열에 대해 2~6번을 반복해 최소 경로를 찾는다

 

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main { //최적경로
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, c_x, c_y, h_x, h_y;
	static int[][] customer;
	static int c_x_temp, c_y_temp;
	static boolean[] visited;
	static int[] permuArr;
	static int count, result;

	public static void permutation(int cnt) {
		if (cnt == N) {
			solve(permuArr);
			c_x = c_x_temp;
			c_y = c_y_temp;
			return;
		}
		for (int i = 0; i < N; i++) {
			if (visited[i])
				continue;
			visited[i] = true;
			permuArr[cnt] = i;
			permutation(cnt + 1);
			visited[i] = false;
		}
	}

	private static void solve(int[] arr) {
		count = 0;
		for (int i : arr) {
			count += Math.abs(c_x - customer[i][0]) + Math.abs(c_y - customer[i][1]);
			c_x = customer[i][0];
			c_y = customer[i][1];
		}
		count += Math.abs(c_x - h_x) + Math.abs(c_y - h_y);
		result = Math.min(count, result);

	}

	public static void main(String[] args) throws Exception {
		int test_case = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= test_case; tc++) {
			N = Integer.parseInt(in.readLine());
			st = new StringTokenizer(in.readLine());
			c_x_temp = Integer.parseInt(st.nextToken());
			c_y_temp = Integer.parseInt(st.nextToken());
			c_x = c_x_temp;
			c_y = c_y_temp;
			h_x = Integer.parseInt(st.nextToken());
			h_y = Integer.parseInt(st.nextToken());
			customer = new int[N][2];
			for (int i = 0; i < N; i++) {
				customer[i][0] = Integer.parseInt(st.nextToken());
				customer[i][1] = Integer.parseInt(st.nextToken());
			}
			result = Integer.MAX_VALUE;
			visited = new boolean[N];
			permuArr = new int[N];
			permutation(0);
			System.out.println("#" + tc + " " + result);

		}
	}
}

 

 

느낀점

 

• 순열이나 조합 등 여러가지를 시도한 다음 최종 해를 구하기 위해서는 초기화!를 꼭 꼼꼼하게 해주어야 한다
• 배열에서 최소 경로 값은 |x1-x2| + |y1-y2|로 구하라고 문제에 나와있는데 괜히 BFS 써서 복잡하게 갈 뻔 했다