[ SWEA / 자바 ] 1247번 최적 경로

📑 문제

회사에서 시작해서 N명의 고객의 집을 들른 후 집으로 향해야 한다.

이때 전체 경로 중 가장 짧은 경로를 찾아 출력하는 문제

 

 

💡 입력

 

✔ 범위 고객의 수 2 ≤ N ≤ 10 좌표의 값 0 ≤ x, y ≤ 100

 

✔ 테스트케이스, 각 테스트케이스의 고객수 N, 회사의 좌표, 집의 좌표, N명의 고객 좌표가 순서대로 입력됨

 

✔ x, y 쌍이 공백으로 구분되어 제공

 

---

---

✨ 풀이 과정

✔ 좌표를 1차원 배열로 각각 받아서 첫째값(회사 위치), 마지막값(집 위치) 를 고정하고 중간 고객 집 주소에 순열을 사용하였다.

 

✔ 회사와 집은 반드시 처음과 마지막에 방문하므로 순열을 이용해 섞을 필요가 없다. 따라서 check 배열을 N개로 만들고 1 ~ N 까지만 방문했는지 안했는지를 따져 result 배열을 채우면 된다

 

✔ (x1 - x2)와 (y1 - y2)의 합을 구하되, 절대값의 합이어야 하므로 Math.abs() 메서드를 이용한다

 

✔ 합을 더하는 중간에 이미 저장되어 있던 거리 합의 최소값보다 커지게 되면 계산을 멈춘다

---

---

📑 코드

import java.util.Scanner;
 
public class Solution {
    static int N; // 고객의 수
    static int[] xrr; // 초기 x값 배열
    static int[] yrr; // 초기 y값 배열
    static int[] resultX; // 결과 배열
    static int[] resultY;
    static int ans; // 최소거리
    static boolean[] check; // 방문 했는지 아닌지
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
             
            xrr = new int[N+2];
            yrr = new int[N+2];
             
            for(int i=0; i<N+2; i++) {
                xrr[i] = sc.nextInt();
                yrr[i] = sc.nextInt();
            } //좌표 채우기
                         
            resultX = new int[N+2];
            resultY = new int[N+2];
             
            resultX[0] = xrr[0]; //첫번째는 무조건 회사 고정
            resultY[0] = yrr[0];
             
            resultX[xrr.length-1] = xrr[1]; //마지막은 집 고정
            resultY[yrr.length-1] = yrr[1];
             
            check = new boolean[N];
             
            ans = Integer.MAX_VALUE;
             
            shortest(1);
             
            System.out.println("#"+tc+" "+ans);
             
        } //테스트케이스
 
    } //main
     
    public static void shortest(int idx) {
         
        //탈출조건
        if(idx == xrr.length-1) {
             
            int X = 0;
             
            for(int i=0; i<N+1; i++) { //거리의 합
                X += Math.abs(resultX[i] - resultX[i+1]) + Math.abs(resultY[i] - resultY[i+1]); 
                 
                if(X>ans) return; 
				//계산하다가 거리의 합이 현재 나와있는 거리의 합 최소값보다 커지면 계산 종료
            }
             
            ans = Math.min(ans, X); //최소값 갱신
 
            return;
        }
         
         
        for(int i=2; i<N+2; i++) {
            if(!check[i-2]) { //아직 안 간 집이다
                resultX[idx] = xrr[i];
                resultY[idx] = yrr[i];
                 
                check[i-2] = true; //갔다고 바꿔주고
                shortest(idx+1); //내려가기
                 
                check[i-2] = false; //다음에 다시 가야 되니까 초기화
                 
            }
        }
    }
 
}

---

---