[SW expert Academy] SWEA 1247번 최적 경로 자바(Java)

[D5] [S/W 문제해결 응용] 3일차 - 최적 경로 - 1247

문제 링크

성능 요약

메모리: 103,844 KB, 시간: 1,449 ms, 코드길이: 2,215 Bytes

제출 일자

2023-12-31 18:34

 

풀이 방법

1. N명의 고객을 방문하고 집으로 간다.

2. 회사, 집 위치, 각 고객의 위치는 이차원 정수 좌표(x,y)로 줌

3. 두 위치 사이는 |x1-x2| + |y1-y2| 로 계산

4. 회사에서 출발하여 모든 고객을 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 함

5. 회사와 집의 좌표, 2~10명 사이 고객 좌표가 주어짐

6. 모두 방문하고 집으로 가는 경로 중 총 이동거리가 가장 짧은 경로의 이동거리 출력

 

a. 브루트 포스로 모든 경우의 수를 출력한다.

b. 클래스 하나 생성 (x,y,distance 출력)

c. 전부 돌고난 후 그 위치에서 집으로 가는 경로를 더 해준 뒤 값을 갱신해준다.

d. 출발점은 무조건 회사. 도착점은 무조건 집

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
    static class Point{
        int x;
        int y;
        int distance;

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

    static int n;
    static boolean[] visit;
    static Point[] customers;
    static Point company, house;
    static int result;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            // 고객의 명수
            n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            // 회사와 집 클래스 생성
            company = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),0);
            house = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),0);

            // 방문 여부를 저장하는 visit와 손님의 좌표를 저장
            visit = new boolean[n];
            customers = new Point[n];
            for(int i = 0; i < n; i++){
                customers[i] = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),0);
            }

            // 최단거리를 찾는 것이기 때문에 result를 MAX_VALUE로 초기화
            result = Integer.MAX_VALUE;
            bruteforce(new Point(company.x, company.y, 0),0);
            sb.append("#" + tc + " " + result).append("\n");
        }
        System.out.println(sb);
    }

    private static void bruteforce(Point pos, int depth){
        // 모든 손님을 방문했다면 집으로 가는 거리를 구한 후 result 갱신
        if(depth == n){
            int answer = calc(pos,house);
            result = Math.min(answer,result);
            return;
        }

        for(int i = 0; i < n; i++){
            // 방문했다면 return
            if(visit[i]) continue;

            // nextDistanceValue를 갱신 후 다음 메서드에 넣어주고 visit를 다시 false
            visit[i] = true;
            int nextValue = calc(pos,customers[i]);
            bruteforce(new Point(customers[i].x, customers[i].y, nextValue),depth+1);
            visit[i] = false;
        }
    }

    // 거리를 계산해준다.
    private static int calc(Point current, Point next){
        return current.distance + Math.abs(current.x - next.x) + Math.abs(current.y - next.y);
    }
}