SWEA 1247 - 최적 경로

Java

1247 번 - 최적 경로

문제

회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)
두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.

회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.
회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,
회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

접근 방법

무식하게 순열을 통하여 해결하였다.
n명의 고객을 순열을 통해 순서를 배정하고, [회사 - 고객 1 ~ 고객 10 - 집]의 거리를 계산한다.
고객이 최대 10명이므로 10! == 3,628,800이며, 고객끼리 계산을 하면 3,628,800 x 9 = 32,659,200으로 아슬아슬하게 1초 미만의 시간이 나올 것 같아 순열로 해결하였다.

구현

우선 인덱스 1 ~ 18 까지 담을 수 있는 전체 카드 배열을 초기화한다.
규영이의 카드를 저장 할 때마다, 위 전체 카드 배열 인덱스에 규영이의 카드 위치를 배정하여 규영이의 카드 위치를 나타낸다.
전체 카드 배열에서 뽑히지 않은 카드를 인영이의 카드로 선언한다.

DFS를 통해 인영이의 9장의 카드 순열을 구현한다.
9장의 카드가 뽑혔을 때, 인영이와 규영이의 카드를 한장 씩 비교하여 더 큰 사람에게 카드의 합 점수를 부여한다.
최종 점수를 비교하여 승패를 결정한다.

코드

import java.io.*;
import java.util.*;
// 회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로
class Solution {
	static int result = 987654321, n;
	static boolean[] vis;
	static Pair[] sel;
	
	static Pair company, house;
	static Pair[] customer;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int idx = 1; idx <= tc; idx++) {
    		result = 987654321;
    		n = stoi(br.readLine());
    		stk = new StringTokenizer(br.readLine());
    		sel = new Pair[n];
    		vis = new boolean[n];
    		company = new Pair(stoi(stk.nextToken()), stoi(stk.nextToken())); 	// 회사
    		house = new Pair(stoi(stk.nextToken()), stoi(stk.nextToken()));		// 집
    		customer = new Pair[n];
    		for(int i = 0; i < n; i++) {
    			customer[i] = new Pair(stoi(stk.nextToken()), stoi(stk.nextToken()));	// 고객
    		}
    		
    		DFS(0);
    		
    		System.out.println("#" + idx + " " + result);
    	}
    	
	}
	// n명의 고객의 집 순서를 배정한다.
	static void DFS(int lv) {
		if(lv == n) {
			// 계산 된 거리 중 최소 거리를 저장한다.
			result = Math.min(Cal(), result);
			return;
		}
		for(int i = 0; i < n; i++) {
			if(!vis[i]) {
				vis[i] = true;
				sel[lv] = customer[i];
				DFS(lv + 1);
				vis[i] = false;
			}
		}
	}
	static int Cal() {
		int sum = 0;
		sum += Math.abs(company.y - sel[0].y) + Math.abs(company.x - sel[0].x);		//회사와 고객1의 거리
		for(int i = 0; i < n - 1; i++) {
			sum += Math.abs(sel[i].y - sel[i + 1].y) + Math.abs(sel[i].x - sel[i + 1].x);	//고객 사이의 거리
		}
		sum += Math.abs(house.y - sel[n - 1].y) + Math.abs(house.x - sel[n - 1].x);	// 고객 n과 집 사이의 거리
		return sum;
	}
	static class Pair{
		int y,x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

단순 무식하게 푼 문제.
동기의 코드를 보니, 백 트래킹으로 가지치기를 하면 훨씬 빠르게 해결 할 수 있다.

개선할 점

음.. 백트래킹으로도 개선해 보자.