[swea] 최적 경로 - java

BruteForce - 순열

처음 푼 풀이... 그냥 단순하게 고객 N명을 방문할 순서를 순열로 만들어서, 해당 순서대로 이동거리를 구해보고,

이동거리가 최소값이라면 갱신하는 방법을 사용하였다.

이는 N이 최대 10이기 때문에 10! = 3628800 로 해결할 수 있는 문제였다.

해당 문제는 시간제한이 20초로.. 없으나 다름없는 문제라 정답으로 인정되긴 했지만,

다른 아이디어로 더 빠르게 풀어보고 싶어졌다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int n;
    static ArrayList<Point> customers; // 고객 좌표를 저장하는 리스트
    static int[] order; // 방문할 고객 index 순서를 저장하는 리스트
    static Point company;
    static Point home;
    static int min_distance;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            order = new int[n];
            st = new StringTokenizer(br.readLine());
            company = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            customers = new ArrayList<Point>();
            for (int i = 0; i < n; i++) {
                customers.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            min_distance = Integer.MAX_VALUE;
            permutation(0, 0);
            sb.append("#").append(t).append(" ").append(min_distance).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
 
    /**
     * 
     * @param cnt  : 지금까지 만든 순열 개수
     * @param flag : 중복 확인을 위한 비트마스킹
     */
    static void permutation(int cnt, int flag) {
        if (cnt == n) {
            // 경로 이동거리 계산하기
            int distance = calculateDistance();
            if (distance < min_distance) {
//              System.out.println("최소경로 순서 " + Arrays.toString(order));
                min_distance = distance;
//              System.out.println("최소 이동거리 " + min_distance);
            }
            return;
        }
 
        for (int i = 0; i < n; i++) {
            if ((flag & (1 << i)) != 0)
                continue; // i번째가 이미 선택된 경우
            order[cnt] = i;
            permutation(cnt + 1, flag | (1 << i)); // i번째를 선택체크한 후 재귀호출
        }
    }
 
    static int calculateDistance() {
        int distance = 0;
        // 첫번째 고객과 회사의 거리 계산
        distance += Math.abs(customers.get(order[0]).x - company.x) + Math.abs(customers.get(order[0]).y - company.y);
        // 2번 고객부터 n번째 고객까지 이동 거리 계산
        for (int i = 0; i < n-1; i++) {
            int x = customers.get(order[i]).x;
            int y = customers.get(order[i]).y;
            int nx = customers.get(order[i+1]).x;
            int ny = customers.get(order[i+1]).y;
            distance += Math.abs(nx - x) + Math.abs(ny - y);
        }
        // n번째 고객에서 집까지 거리 계산
        distance += Math.abs(customers.get(order[n-1]).x - home.x) + Math.abs(customers.get(order[n-1]).y - home.y);
        return distance;
    }
 
}

 

dp & bit mask

예~~~전에 traveling salesman problem (TSP) 알고리즘을 풀어본 적이 있었는데, 내 기억에서 사라졌었나 보다.

TSP 의 개념을 다시 익힌 후, 문제를 풀어보았다.

그리고 중복처리를 하기 위해 요즘 애용하고 있는 bit mask 를 응용해서 사용해보았다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {

	static int n;
	static ArrayList<Point> nodes; // 고객 좌표를 저장하는 리스트
	static Point home;
	static int min_distance;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

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

		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			
			// 회사는 첫 번째 노드로 지정
			nodes = new ArrayList<Point>();
			nodes.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
	
			// 고객 좌표 저장
			for (int i = 1; i <= n; i++) {
				nodes.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			}

			// dp[i][visited] => 지금까지 방문한 노드집합이 visited일때, 방문하지 않은 노드들을 모두 방문했을 때의 최소 비용
			dp = new int[n+1][1 << (n + 1)]; 
			for(int i=0; i<n+1; i++)
				Arrays.fill(dp[i], Integer.MAX_VALUE);
			
			min_distance = dfs(0,1); // 집을 현재노드로 하여, 방문한 상태
			
			sb.append("#").append(t).append(" ").append(min_distance).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	/**
	 * 
	 * @param now : 현재 내가 위치한 노드
	 * @param flag : 현재까지 방문한 노드들의 집합을 표시하는 비트마스킹
	 * @return
	 */
	static int dfs(int now, int flag) {
		if (flag == (1 << n + 1) - 1) { // 회사부터 시작해서 모든 고객 노드를 방문한 경우
			// 현재 노드에서 집까지의 거리를 계산하기
			return getDistance(home.x, home.y, nodes.get(now).x, nodes.get(now).y); 
		}
		
		if (dp[now][flag] != Integer.MAX_VALUE) // 이미 dp값이 갱신된 경우라면 리턴하기
			return dp[now][flag];
		
		// 회사는 0번째 인덱스이므로 제외하고 탐색
		for(int i=1; i<=n; i++) { // 1번째고객부터 n번째 고객까지 방문하기
			if ((flag & (1<<i)) != 0) continue; // i노드가 이미 방문한 노드라면 continue
			
			// dp[now][flag] = dp[now][flag] or dp[i][flag | (1<<i)] + (i~now)노드간의 거리 중 최솟값 
			// dp[i][flag | (1<<i)] 을 구하기 위해 i를 now로 해서 dfs를 호출한다.
			dp[now][flag] = Math.min(dp[now][flag], getDistance(nodes.get(now).x, nodes.get(now).y, nodes.get(i).x, nodes.get(i).y)+ dfs(i, flag | (1<<i)));	
		}
		return dp[now][flag];
	}

	static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}

}

 

아이디어

TSP 알고리즘은 다음과 같다.

여러 지역을 돌면서 물건을 판매해야 하는 판매원이, 모든 지역을 돌고 다시 출발점으로 돌아와야 한다고 할 때, 가장 최적의 경로를 찾는 문제

이를 어떻게 dp로 해결할 수 있을까?

 

 

1~n번 노드가 있고, 이 중 몇 개의 노드를 거친 후에 지금 판매원이 i번 노드에 있다.
그렇다면 아직 방문하지 않은 노드들 중에서 다음 노드를 정해야 한다.

 

총 5개의 노드를 방문해야 하고, 이 중 1, 2번 노드를 돌았다고 가정해보자.

방문하지 않은 노드는 3, 4, 5번 이다.

이 때 우리는 3가지 경우의 수를 생각할 수 있다.

• 3번 도시를 방문 + 나머지 4, 5번 도시를 최적으로 해결
• 4번 도시를 방문 + 나머지 3, 5번 도시를 최적으로 해결
• 5번 도시를 방문 + 나머지 3, 4번 도시를 최적으로 해결

3,4,5 중 하나의 도시를 방문했을 때 최솟값을 가지는 경우, 해당 도시를 방문하게 된다.
즉, 현재 상태에서 남은 노드들을 최적 경로로 돌았을 때의 총 거리 가 최솟값이 되어야 한다.

 

 

이제 2차원 배열 dp[i][visited] 를 정의해보자.

현재까지 방문한 노드들의 집합은 visited이고, 현재 위치는 i라고 할 때,
남은 노드들을 최소 거리로 돌았을 때의 총 이동 거리

 

점화식을 세워보면 다음과 같다.

dp[i][visited] 는 기존의 값 혹은

i에서 visited에 해당하지 않는 노드 j 까지의 거리 + dp[j][visited | (1<<j) 둘 중 최솟값으로 구할 수 있다.

이때 dp[j][visited | (1<<j)] 는 j를 now로 간주하고, visited 에서 j의 방문을 표시한 visited | (1<<j) 을 인자로 받는 DFS로 구할 수 있다.

즉, 현재의 dp값을 구하기 위해선, 더 작은 dp로 쪼개어 dfs를 재귀호출하여 문제를 해결해야 한다.

dp[i][visited] = min(dp[i][visited], dp[j][visited | (1 << j)] + dist[i][j])

 

이 문제에서는 첫 번째(0번째 인덱스) 노드가 회사로 고정되어 있다.

따라서 회사는 이미 방문했음으로 가정하고, now = 1, flag = 1 을 인자로 DFS를 호출한다.

 

다음에 방문할 노드를 for문을 통해 i=1~n까지 탐색해본다.

만약 i번째 노드가 flag에 포함되어있지 않다면, i번째 노드 부터 시작하여 끝 노드까지의 최소 이동 거리를 dfs로 구한다.

 

만약, 방문표시를 하는 bit mask 가 다음과 같다면? 모든 노드를 방문한 것이다.

예를 들어, 5개의 노드를 모두 방문한 경우에는 11111과 같을 것이므로, 1<<6인 10000 에서 - 1을 해준것이다.

즉, 모든 노드를 방문한 경우에는 now가 마지막 노드이므로, now에서부터 home 까지의 거리를 계산해서 리턴해주면 된다.