[SWEA] S/W 문제해결 응용 1247 최적경로

1247 최적경로

난이도 : D5
유형 : 순열, 완전탐색, 백트래킹

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD

문제

삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다.

회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)

두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.

여기서 |x|는 x의 절대값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다.

회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.

회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,

회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.

이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.

여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.

모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.

제약사항

고객의 수 N은 2≤N≤10 이다.

그리고 회사의 좌표, 집의 좌표를 포함한 모든 N+2개의 좌표는 서로 다른 위치에 있으며 좌표의 값은 0이상 100 이하의 정수로 이루어진다.

입력

가장 첫줄은 전체 테스트케이스의 수이다.

이후, 두 줄에 테스트 케이스 하나씩이 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 고객의 수 N이 주어진다. 둘째 줄에는 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다.

좌표는 (x,y)쌍으로 구성되는데 입력에서는 x와 y가 공백으로 구분되어 제공된다.

출력

총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 최단 경로의 이동거리를 기록한다. 여기서 x는 테스트 케이스의 번호다.

풀이

회사에서 출발해서 모든 고객의 집을 방문하고 집으로 돌아가는 경로의 최단 경로를 찾는 문제다. 문제에서 제시한대로 가장 짧은 경로를 효율적으로 찾는 것이 목적이 아니기 때문에 완전탐색으로도 충분히 풀 수 있는 문제였다. 하지만 나는 완전탐색보다는 조금 빠른 순열을 이용해서 풀어보았다.
순열로 풀어본 결과 실행시간이 2,449ms나 나왔다. 너무 많이 나온거 같아 백트래킹을 적용해주었더니 289ms로 9배가량 시간을 단축할 수 있었다.

코드

1. 순열이용

import java.io.*;
import java.util.StringTokenizer;
 
public class Solution {
     
    static int T, N;
    static int answer;
    static int [][] location;
    static int [][] numbers;
     
    static boolean isVisited[];
     
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
         
        T = Integer.parseInt(br.readLine());
         
        for(int t=1; t<=T; t++) {
            answer = Integer.MAX_VALUE;
            N = Integer.parseInt(br.readLine());    // 고객 수
            location = new int[N+2][2]; // 좌표 위치 담을 배열
            numbers = new int[N][2];
            isVisited = new boolean[N];
            st = new StringTokenizer(br.readLine());
            // 시작 위치
            location[0][1] = Integer.parseInt(st.nextToken());
            location[0][0] = Integer.parseInt(st.nextToken());
             
            // 끝나는 위치
            location[N+1][1] = Integer.parseInt(st.nextToken());
            location[N+1][0] = Integer.parseInt(st.nextToken());
             
            for(int i=1; i<N+1; i++) {
                location[i][1] = Integer.parseInt(st.nextToken());
                location[i][0] = Integer.parseInt(st.nextToken());
            }
             
            permu(0);
             
            System.out.println("#"+t+" "+answer);
        }
    }
     
    public static void permu(int cnt) {
        if(cnt==N) {
            int sum = 0;
            int r = location[0][0];
            int c = location[0][1];
             
            for(int i=0; i<N; i++) {
                sum += Math.abs(r-numbers[i][0]);
                sum += Math.abs(c-numbers[i][1]);
                r = numbers[i][0];
                c = numbers[i][1];
            }
             
            sum += Math.abs(location[N+1][0] - r);
            sum += Math.abs(location[N+1][1] - c);
             
            answer = Math.min(answer, sum);
             
            return;
        }
         
        for(int i=0; i<N; i++) {
            if(!isVisited[i]) {
                isVisited[i] = true;
                numbers[cnt] = location[i+1];
                permu(cnt+1);
                isVisited[i] = false;
            }
        }
    }
 
}

2. 백트래킹 이용

import java.io.*;
import java.util.StringTokenizer;

/**
 * SWEA_1247_D5_최적경로
 * @author mingggkeee
 *
 */

public class SWEA_1247 {
	
	static int T, N;
	static int answer;
	static int [][] location;
	static int startR, startC, endR, endC;
	
	static boolean isVisited[];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			answer = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());	// 고객 수
			location = new int[N][2];	// 좌표 위치 담을 배열
			isVisited = new boolean[N];
			st = new StringTokenizer(br.readLine());
			// 시작 위치
			startC = Integer.parseInt(st.nextToken());
			startR = Integer.parseInt(st.nextToken());
			
			// 끝나는 위치
			endC = Integer.parseInt(st.nextToken());
			endR = Integer.parseInt(st.nextToken());
			
			for(int i=0; i<N; i++) {
				location[i][1] = Integer.parseInt(st.nextToken());
				location[i][0] = Integer.parseInt(st.nextToken());
			}
			
			permu2(0,0,startR, startC);
			
			sb.append("#").append(t).append(" ").append(answer).append("\n");
			
		}
		
		System.out.println(sb.toString());
	}
	
	public static void permu2(int cnt, int sum, int r, int c) {
		
		if(sum>answer) {
			return;
		}
		
		if(cnt==N) {
			sum += Math.abs(endR -r);
			sum += Math.abs(endC -c);
			answer = Math.min(answer, sum);
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!isVisited[i]) {
				isVisited[i] = true;
				sum += Math.abs(location[i][0] - r);
				sum += Math.abs(location[i][1] - c);
				permu2(cnt+1, sum, location[i][0], location[i][1]);
				isVisited[i] = false;
				sum -= Math.abs(location[i][0] - r);
				sum -= Math.abs(location[i][1] - c);
			}
		}
	}

}