[백트래킹] 1247. 최적경로 (Java)

[SWEA] 1247. 최적경로

📝 풀이 과정

문제 개요

이 문제는 회사에서 출발하여 모든 고객을 방문한 뒤, 집으로 돌아오는 최단 경로를 찾는 문제다. 목표는 이 경로의 거리를 최소화하는 것이다.

알고리즘 설명

이 문제는 백트래킹 알고리즘을 사용해 해결한다. 백트래킹을 사용하면 가능한 모든 경로를 탐색하면서, 그중 최단 경로를 찾을 수 있다.

풀이 과정

1. 초기 설정:

   • 입력으로 주어진 회사, 집, 그리고 각 고객들의 위치를 position 배열에 저장한다.
   • 각 고객을 방문했는지 여부를 추적하기 위해 visited 배열을 사용한다.
   • 최소 거리를 저장하기 위해 minDistance를 초기화한다.

2. DFS(깊이 우선 탐색) 시작:

   • dfs 함수는 현재 위치(cur), 방문한 고객 수(depth), 그리고 현재까지의 거리 합계(sum)를 인자로 받는다.
   • dfs는 모든 고객을 방문할 때까지 재귀적으로 호출된다.

3. 가지치기:

   • 만약 현재까지의 거리 합계(sum)가 이미 계산된 최소 거리(minDistance)보다 크다면, 더 이상 탐색하지 않고 중단한다. 이를 가지치기라고 하며, 탐색 공간을 줄이는 데 중요한 역할을 한다.

4. 기저 조건:

   • 모든 고객을 방문한 경우(depth == N), 현재 위치에서 집까지의 거리를 계산하여 sum에 더한다.
   • 이 값이 minDistance보다 작다면 minDistance를 갱신한다.

5. 다음 고객 방문:

   • 아직 방문하지 않은 고객들을 찾아가며, 방문 상태를 갱신하고 재귀적으로 dfs를 호출한다.
   • 재귀 호출이 끝난 후에는 해당 고객의 방문 상태를 되돌려 다른 경로를 탐색할 수 있도록 한다.

최적화

• 가지치기: 불필요한 경로 탐색을 미리 차단하여 실행 시간을 크게 단축한다.
• 2차 시도에서 sum > minDistance 조건을 추가하여, 실행 시간을 대폭 줄이는 데 성공했다 (1차 시도: 1,830 ms → 2차 시도: 281 ms).

이 과정을 통해 모든 가능한 경로를 탐색하며 최적의 경로를 찾아내는 것이 이 문제의 핵심이다.

👩🏻‍💻 제출 코드

1차 시도

메모리 20,704 kb
실행 시간 1,830 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int N, minDistance;
    static int[][] position;
    static boolean[] visited;
    static int[] turn;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스
 
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); // 고객의 수
            position = new int[N+2][2];
            visited = new boolean[N+2];
            turn = new int[N + 2];
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N+2; i++) {
                position[i][0] = Integer.parseInt(st.nextToken());
                position[i][1] = Integer.parseInt(st.nextToken());
            }
 
            minDistance = Integer.MAX_VALUE;
            visited[0] = true; // 회사는 이미 방문한 것으로 설정
            turn[0] = 0;
            dfs(1); // 회사에서 출발, depth 1부터 시작
 
            System.out.println("#" + t + " " + minDistance);
        }
    }
 
    public static void dfs(int depth) {
        if(depth == N + 1) {
            turn[depth] = 1;
            int distance = 0;
            for(int i = 0; i < N + 1; i++) {
                distance +=  Math.abs(position[turn[i]][0] - position[turn[i+1]][0])
                    +  Math.abs(position[turn[i]][1] - position[turn[i+1]][1]);
            }
 
            minDistance = Math.min(distance, minDistance);
            return;
        }
 
        for(int i = 2; i < N + 2; i++) { // 2번부터 N+1번까지 고객
            if(visited[i]) continue;
 
            turn[depth] = i; // 방문 순서 저장
            visited[i] = true;
            dfs(depth + 1);
            visited[i] = false;
        }
    }
 
}

2차 시도

메모리 20,604 kb
실행 시간 281 ms

package D5;

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

public class 최적경로_1247 {

    static int N, minDistance;
    static int[][] position;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); // 고객의 수
            position = new int[N+2][2];
            visited = new boolean[N+2];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N+2; i++) {
                position[i][0] = Integer.parseInt(st.nextToken());
                position[i][1] = Integer.parseInt(st.nextToken());
            }

            minDistance = Integer.MAX_VALUE;
            dfs(0, 0, 0); // 회사에서 출발, depth 1부터 시작

            System.out.println("#" + t + " " + minDistance);
        }
    }

    public static void dfs(int cur, int depth, int sum) {
        if(sum > minDistance) return;

        if(depth == N) {
            // 마지막 고객에서 집까지 거리
            sum += Math.abs(position[cur][0] - position[1][0]) + Math.abs(position[cur][1] - position[1][1]);
            minDistance = Math.min(sum, minDistance);
            return;
        }

        for(int i = 2; i < N + 2; i++) { // 2번부터 N+1번까지 고객
            if(visited[i]) continue;

            visited[i] = true;

            int nextDistance = sum + Math.abs(position[cur][0] - position[i][0])
                +  Math.abs(position[cur][1] - position[i][1]);
            dfs(i, depth + 1, nextDistance);
            visited[i] = false;
        }
    }

}