[Swea] 최적 경로 - Java

문제

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

SW Expert Academy

 

문제 요약

1. 김대리는 회사에서 출발
2. 김대리는 모든 고객의 집 방문
3. 이후 집 도착

위 조건으로 집, 회사, 고객의 집 좌표 정보를 이용해, 최단 거리를 구하는 문제이다.

 

문제 풀이

고객의 수 = 2~10

x, y 좌표 = 0~100

 

10개의 집을 순서대로 나열하는 경우의 수를 구하면

10! = 약 300만이다.

 

좌표상 최장거리 =  200, 10개의 집

최고 거리 = 200 * 10이다.

즉, Integer 범위로 해결할 수 있다.

 

첫번째 집부터 방문해서 모든 집을 방문하면서 거리 계산

두번째 집부터 방문해서 모든 집을 방문하면서 거리 계산

...

마지막 집부터 방문해 모든 집을 방문하면서 거리 계산

 

거리 계산에서 유의해야할 점은 모든 고객의 집을 방문한 이후, 김대리의 집까지의 거리를 더해줘야한다.

 

dfs로 방문 처리하면서 순회한다.

 

소스코드

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

public class Solution {
    private static int answer;
    private static int n;
    private static int destX, destY;

    private static boolean[] visited;
    private static int[] x;
    private static int[] y;

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

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

        StringBuilder sb = new StringBuilder();

        for (int testCase = 1; testCase <= tc; testCase++) {
            sb.append("#").append(testCase).append(" ");

            n = Integer.parseInt(br.readLine());
            answer = Integer.MAX_VALUE;

            x = new int[n];
            y = new int[n];
            visited = new boolean[n];

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

            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());

            destX = Integer.parseInt(st.nextToken());
            destY = Integer.parseInt(st.nextToken());

            for (int i = 0; i < n; i++) {
                x[i] = Integer.parseInt(st.nextToken());
                y[i] = Integer.parseInt(st.nextToken());
            }

            dfs(0, 0, startX, startY);

            sb.append(answer).append("\n");
        }

        System.out.print(sb);

        br.close();
    }

    private static void dfs(int distance, int depth, int curX, int curY) {
        if (answer < distance) {
            return;
        }

        if (depth == n) {
            //마지막 고객에서 집까지의 거리를 구함
            int destLength = Math.abs(curX - destX) + Math.abs(curY - destY);
            answer = Math.min(answer, distance + destLength);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;

                int length = Math.abs(x[i] - curX) + Math.abs(y[i] - curY);

                dfs(distance + length, depth + 1, x[i], y[i]);

                visited[i] = false;
            }
        }
    }
}