[SWEA | Java] 1247번 최적 경로

문제

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

SW Expert Academy

티어

소요 시간

20분

분류

dfs

코드

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

public class Solution {

    static public class Location {
        int x, y;

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

    static int n;
    static ArrayList<Location> locations;
    static Location company;
    static Location house;

    static int res;

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

        int t = Integer.parseInt(st.nextToken());
        for (int test = 1; test <= t; test++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            locations = new ArrayList<>();
            for (int i = 0; i < n + 2; i++) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                if (i == 0) {
                    company = new Location(x, y);
                }
                else if (i == 1) {
                    house = new Location(x, y);
                }
                else {
                    locations.add(new Location(x, y));
                }
            }

            res = Integer.MAX_VALUE;
            dfs(company, 0, 0, new boolean[n]);

            System.out.println("#" + test + " " + res);
        }
    }

    private static void dfs(Location cur, int cnt, int totalDist, boolean[] visited) {
        if (cnt == n) {
            res = Math.min(res, totalDist + Math.abs(cur.x - house.x) + Math.abs(cur.y - house.y));
        } else if (totalDist < res){
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    Location next = locations.get(i);
                    dfs(next, cnt + 1, totalDist + Math.abs(cur.x - next.x) + Math.abs(cur.y - next.y), visited);
                    visited[i] = false;
                }
            }
        }
    }
}

코드 설명

문제에서 모든 경우를 체계적으로 따지면 답을 구할 수 있다고 되어있는데 이 경우 통과는 하지만 시간 복잡도가 1000ms가 넘게 된다.

약간의 최적화를 거치면 시간을 단축할 수 있다.

 

모든 경우를 체계적으로 따진다는 의미는 회사에서 출발해서 모든 경로에 대해서 구해본다는 의미이다.

하지만 구하지 않아도 되는 경우가 있다.

바로 지금까지 구한 거리의 최솟값이 현재 루트에서 구한 거리보다 작다면 그 루트는 더 이상 탐색을 하지 않아도 된다.