SWEA 1247번: 최적 경로 Java Solution

1. Problem Definition & Analysis

회사 - 특정 경로 - 집으로 연결되는 최소 비용을 갖는 경로의 비용을 찾는 문제이다. 문제 설명에도 나와 있듯이 효율이 중요한 문제는 아니다. $2 \le N \le 10$으로 제약 조건이 매우 널널하고 테스트 케이스도 10개밖에 없으므로 어떤 해결 방법이든 유효할 것으로 보인다.

나는 두 가지 풀이를 생각해 보았다.

1. 순열 기반의 풀이법: $N$명의 고객의 방문 순서를 순열으로 미리 결정한 후 비용을 계산하는 방식이다. 예를 들어 고객이 $3$명 있다면 $(1 \to 2 \to 3)$, $(2 \to 1 \to 3)$, $(2 \to 3 \to 1)$, $...$ 등으로 방문 순서를 결정한다. 이 방식의 시간 복잡도는 $O(N!)$이다.
2. DP 기반의 풀이법: 이 문제를 외판원 순회 문제(TSP, Traveling Salesman Problem)의 일종이라고 생각하고 Bismasking DP를 사용해 해결하는 것이다. 외판원 순회 문제란 그래프상의 어떤 정점으로부터 다른 모든 정점을 방문한 후 출발 정점으로 되돌아올 때의 최소 비용을 구하는 문제이다. 이 방식의 시간 복잡도는 $O(N \times 2^N)$이다.

시간 복잡도를 비교해 보았을 때 2번 풀이가 효율적이라고 생각되어 2번 풀이를 따르기로 결정했다.

2. Solution

package P1247;

import java.io.*;
import java.util.*;

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static class Coords {
        int x, y;

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

        public int getDistance(Coords other) {
            return Math.abs(x - other.x) + Math.abs(y - other.y);
        }
    }

    static final int INF = Integer.MAX_VALUE;
    static final int COMPANY = 0;
    static final int HOME = 1;

    static int T, N;
    static Coords[] coords;
    static int[][] cache;

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++)
            sb.append('#').append(i).append(' ').append(solve()).append('\n');
        System.out.println(sb);
    }

    public static int solve() throws IOException {
        N = Integer.parseInt(br.readLine());
        coords = new Coords[N + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i <= N + 1; i++) {
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            coords[i] = new Coords(x, y);
        }
        cache = new int[N + 2][1 << N + 2];
        for (int[] row : cache)
            Arrays.fill(row, INF);
        return DFS(COMPANY, 3);
    }

    public static int DFS(int prev, int mask) {
        if (mask == (1 << N + 2) - 1)
            return coords[prev].getDistance(coords[HOME]);
        else if (cache[prev][mask] != INF)
            return cache[prev][mask];

        for (int i = 2; i < N + 2; i++)
            if ((mask & (1 << i)) == 0)
                cache[prev][mask] = Math.min(cache[prev][mask], coords[prev].getDistance(coords[i]) + DFS(i, mask | (1 << i)));

        return cache[prev][mask];
    }
}

핵심 코드 블럭을 하나씩 살펴보겠다.

    static class Coords {
        int x, y;

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

        public int getDistance(Coords other) {
            return Math.abs(x - other.x) + Math.abs(y - other.y);
        }
    }

우선 그래프의 정점에 해당하는 클래스는 위와 같이 정의했다.

    public static int solve() throws IOException {
        N = Integer.parseInt(br.readLine());
        coords = new Coords[N + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i <= N + 1; i++) {
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            coords[i] = new Coords(x, y);
        }
        cache = new int[N + 2][1 << N + 2];
        for (int[] row : cache)
            Arrays.fill(row, INF);
        return DFS(COMPANY, 3);
    }

전형적인 Bitmasking DP 알고리즘을 사용했으나 특이한 점이 있다. 회사와 집은 이미 방문 순서가 결정되어 있기 때문에 깊이 우선 탐색에서 고려될 필요가 없다. 회사 정점의 인덱스는 0, 집 정점의 인덱스는 1이다. 그래서 $3(= 2^0 + 2^1)$을 초기 마스크 값으로 설정했다.

    public static int DFS(int prev, int mask) {
        if (mask == (1 << N + 2) - 1)
            return coords[prev].getDistance(coords[HOME]);
        else if (cache[prev][mask] != INF)
            return cache[prev][mask];

        for (int i = 2; i < N + 2; i++)
            if ((mask & (1 << i)) == 0)
                cache[prev][mask] = Math.min(cache[prev][mask], coords[prev].getDistance(coords[i]) + DFS(i, mask | (1 << i)));

        return cache[prev][mask];
    }

DFS의 매개변수로는 prev(직전에 방문한 정점), mask(방문 여부를 나타내기 위한 비트 마스크)를 정의하였고, 모든 정점 방문 시 마지막으로 방문한 고객 정점과 집 정점 간의 거리를 계산해 반환하도록 구현했다.