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

문제 링크: (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD)

SW Expert Academy

 

1. 문제 핵심

회사 -> 모든 고객 방문 -> 집
이동 거리의 총합이 최소가 되도록 경로를 구하는 문제

“모든 고객을 방문하는 순서를 정하라” 즉, 순열 문제이다 !

 

2. 문제 풀이

다른 dfs와 같이

• 고객 방문 순서를 모두 탐색
• 각 경로마다 거리 계산
• 최소값 갱신

을 반복하며, 최소값을 찾는다!

• dfs(depth, index, sum)

 

depth	방문한 고객 수
index	현재 위치한 고객
sum	지금까지 이동 거리

• 회사에서 갈 첫 고객 선택

 

for(int i = 0; i < N; i++){
    visited[i] = true;
    dfs(1, i, calculate(cus.get(i), company));
    visited[i] = false;
}

 

 

• 모든 고객 방문 → 집까지 거리 추가

if(depth == N){
    sum += calculate(cus.get(index), house);
    min = Math.min(sum, min);
    return;
}

 

• 가지치기

if(sum >= min) return;

 

이미 최적보다 크면 탐색 중단

• 다음 고객 탐색

 

for(int i = 0; i < N; i++){
    if(visited[i]) continue;

    visited[i] = true;
    dfs(depth+1, i, sum + calculate(cus.get(index), cus.get(i)));
    visited[i] = false;
}

 

3. 코드 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
class Solution
{
    static int N;
    static Node house;
    static Node company;
    static List<Node> cus;
    static boolean[] visited;
    static int min;
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
		for(int test_case = 1; test_case <= T; test_case++)
		{
            sb.append("#").append(test_case).append(" ");
            N = Integer.parseInt(br.readLine());
            visited = new boolean[N];
            cus = new ArrayList<>();
            st = new StringTokenizer(br.readLine());

            company = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            house = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            for(int i = 0; i < N; i ++){
                  cus.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            
            
            min = Integer.MAX_VALUE;
            for(int i =0; i < N; i++){
                visited[i] = true;
                dfs(1, i, calculate(cus.get(i), company));
                visited[i] = false;
            }
            sb.append(min).append("\n");
        }
        
        System.out.print(sb);
	}
    
    public static void dfs(int depth, int index, int sum){
        if( sum >= min) return;
        
        if(depth == N){
            sum += calculate(cus.get(index), house);
            min = Math.min(sum, min);
            return;
        }
        
        for(int i = 0; i <N; i++){
            if(visited[i]) continue;
            
            visited[i] = true;
            dfs(depth+1, i, sum + calculate(cus.get(index), cus.get(i)));
            visited[i] = false;
        }
    }
    
    public static int calculate(Node now, Node next){
        return Math.abs(now.i - next.i) + Math.abs(now.j - next.j);
    }
            

    
    public static class Node{
        int i, j;
        public Node(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}