[SWEA 1247] 최적 경로

문제

• SWEA 1247번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

회사좌표와 집좌표는 고정되므로 집좌표들의 순열을 구하고 나서 각 거리를 계산해 최소 거리를 구하면 되는 문제이다.
순열을 만들어야 하는 이유는 예를 들어 A→B→C와 B→C→A모두 순서에 따라 거리가 다르게 결정되기 때문이다.
나는 입력 받을 때 회사좌표와 집좌표 고객좌표 순서를 제대로 하지못해서 어이없게 3시간이동안 고민을 했다… 너무 어렵게 생각하지 않으면 쉽게 풀리는 문제!!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

//최적경로 - 순열
public class Swea_1247 {

	static int N; // 고객의 수
	static Point[] NList; // 고객 좌표 담을 배열
	static boolean[] visited; // 순열 방문 체크 배열
	static Point[] selected; // 순열 선택 배열
	static int Answer; // 가장 짧은 경로
	static Point company; // 회사 좌표
	static Point home; // 집 좌표
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int totalCnt = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= totalCnt; tc++) {
			N = Integer.parseInt(br.readLine());

			NList = new Point[N];
			visited = new boolean[N];
			selected = new Point[N];

			st = new StringTokenizer(br.readLine());

			// 회사 좌표
			company = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			// 집 좌표
			home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			// 고객 좌표
			for (int i = 0; i < N; i++) {
				NList[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}

			// 고객 순열을 만들어서 경우의 수 구하기
			Answer = Integer.MAX_VALUE; // 최소 거리
			permutation(0);
			System.out.println("#" + tc + " " + Answer);
		}
	}

	static List<Point> list;

	// 순열 계산
	static void permutation(int idx) { // idx: 선택한 고객 인덱스

		int length = 0;
		if (idx == N) {
			//1. 회사 -> 고객 거리
			length += getDist(company, selected[0]);
			
			//2. 고객 끼리의 거리
			for(int i=0; i<selected.length-1; i++) 
				length += getDist(selected[i], selected[i+1]);
			
			//3. 고객 -> 집까지의 거리
			length += getDist(selected[selected.length-1], home);
			Answer = Answer > length ? length : Answer; 
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) { // 중복 방지
				visited[i] = true;
				selected[idx] = NList[i];
				permutation(idx + 1);
				visited[i] = false; // 다음 턴에서 또 뽑을 수 있도록
			}
		}
	}

	// 두 좌표 사이의 거리 계산
	static public int getDist(Point p1, Point p2) {
		return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	}

	// 좌표정보 클래스
	static class Point {
		private int x;
		private int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}