[SWEA 1247] 최적 경로 - JAVA

WTS·2026년 7월 31일
DFSSWEATSP비트마스킹코딩테스트

코딩 테스트

목록 보기
92/93

문제 정의

  • 회사, 집, NN개의 고객 위치(좌표)가 주어짐

회사에서 출발해 모든 고객을 만난 후 집으로 이동하는 최단 경로를 구해라

접근 방법

문제를 처음 확인했을 때 떠오른 방법은 순열 DFS와 외판원 순회 문제(TSP)였습니다.

이 문제는 회사에서 출발하여 모든 고객을 한 번씩 방문한 뒤
집으로 이동하는 경로 중 최단 거리를 구해야 합니다.

고객을 방문하는 순서에 따라 전체 이동 거리가 달라지므로,
가능한 모든 고객 방문 순서를 확인하는 순열 탐색으로 해결할 수 있습니다.

고객 수 NN이 10 이하이기 때문에 우선 순열 DFS로 문제를 해결했습니다.
이후 동일한 상태의 중복 계산을 줄이기 위해 비트마스킹 DP를 적용한 풀이도 구현했습니다.

순열 DFS 풀이

DFS에서는 현재 위치에서 아직 방문하지 않은 고객을 한 명씩 선택합니다.

고객을 방문하기 전에 방문 상태를 true로 변경하고, 해당 경로의 재귀 탐색이 끝난 뒤 다시 false로 복구합니다.

visited[next] = true;
dfs(next, visitedCount + 1, distance + edge.w);
visited[next] = false;

이러한 백트래킹을 통해 하나의 방문 순서를 탐색한 뒤 다른 방문 순서를 계속 확인할 수 있습니다.

모든 고객을 방문했다면 현재 위치에서 집까지의 거리를 더해 최솟값을 갱신합니다.

고객 NN명의 모든 방문 순서는 총 N!N!개이므로, 단순 순열 DFS의 최악 시간 복잡도는 다음과 같습니다.

O(N!)O(N!)

고객 수가 최대 10명이므로 단순 순열 DFS로도 문제를 해결할 수 있지만, 실제 탐색량을 줄이기 위해 가지치기를 적용했습니다.

현재 최솟값을 이용한 가지치기

DFS 탐색 중 모든 고객을 방문하고 집까지 이동하는 하나의 완성 경로를 찾으면 minDistance를 갱신합니다.

minDistance = Math.min(minDistance, distance + homeDistance);

이후 다른 경로를 탐색할 때 현재까지의 누적 거리가 이미 minDistance 이상이라면 더 이상 탐색할 필요가 없습니다.

if (distance >= minDistance) return;

이 문제에서 각 이동 거리는 음수가 될 수 없습니다.

따라서 현재까지의 누적 거리가 이미 최솟값 이상이라면, 남은 고객을 추가로 방문할수록 거리는 같거나 더 증가하게 됩니다.

즉, 다음 조건을 만족하는 경로는 최적해가 될 수 없습니다.

currentDistance≥minDistance\text{currentDistance} \ge \text{minDistance}

이러한 경로를 미리 종료하여 의미 없는 재귀 호출을 줄일 수 있습니다.

거리순 탐색을 통한 가지치기 강화

각 정점에서 다른 정점까지의 거리를 인접 리스트에 저장한 뒤, 거리 기준으로 오름차순 정렬했습니다.

Collections.sort(graph[current]);

이를 통해 DFS는 현재 위치에서 가까운 고객부터 먼저 탐색합니다.

가까운 고객부터 방문한다고 해서 항상 전체 최적 경로가 만들어지는 것은 아닙니다.

현재 위치에서 가장 가까운 고객을 먼저 방문하더라도, 해당 고객에서 나머지 고객까지의 거리가 매우 멀 수 있기 때문입니다.

따라서 이 정렬은 정답을 구하기 위한 그리디 알고리즘이 아닙니다.

정렬의 목적은 비교적 짧은 완성 경로를 초기에 발견할 가능성을 높여 minDistance를 빠르게 작은 값으로 갱신하는 것입니다.

minDistance가 작아질수록 다음 가지치기가 더 자주 발생합니다.

if (distance >= minDistance) return;

정리하면 거리순 정렬은 다음과 같은 역할을 합니다.

가까운 고객부터 탐색
→ 비교적 짧은 완성 경로를 먼저 발견할 가능성 증가
→ minDistance가 빠르게 감소
→ 이후 경로에서 가지치기 발생 가능성 증가

정렬은 탐색 순서만 변경할 뿐, 필요한 경로를 제외하지 않습니다. 따라서 정답의 정확성에는 영향을 주지 않습니다.

다만 최악의 경우에는 정렬하더라도 가지치기가 충분히 발생하지 않을 수 있으므로 시간 복잡도는 여전히 다음과 같습니다.

O(N!)O(N!)

비트마스킹 DP 풀이

순열 DFS에서는 서로 다른 방문 순서로 동일한 상태에 도착하더라도 이후 경로를 다시 계산합니다.

예를 들어 다음 두 경로를 생각해볼 수 있습니다.

회사 → 1 → 3 → 2
회사 → 3 → 1 → 2

두 경로는 고객을 방문한 순서와 현재까지의 이동 거리가 서로 다를 수 있습니다.

하지만 두 경로 모두 다음 상태에 도착했다고 가정해보겠습니다.

현재 위치: 고객 2
방문한 고객: {1, 2, 3}

이 상태에서 남아 있는 고객과 현재 위치가 같다면, 앞으로 남은 고객을 모두 방문하고 집까지 가는 최소 추가 비용은 동일합니다.

즉, 과거에 어떤 순서로 현재 상태에 도착했는지는 이후 경로를 계산할 때 필요하지 않습니다.

따라서 다음과 같이 DP 상태를 정의할 수 있습니다.

dp[mask][current]

dp[mask][current]의 의미는 다음과 같습니다.

mask에 표시된 고객을 이미 방문했고 현재 위치가 current일 때, 남은 고객을 모두 방문하고 집까지 이동하는 최소 추가 거리

비트마스크 정의

비트마스크에는 회사와 집을 제외한 고객 NN명의 방문 여부만 저장합니다.

고객 1 → 0번 비트
고객 2 → 1번 비트
고객 3 → 2번 비트
...
고객 N → N - 1번 비트

고객 번호가 next일 때 해당 고객을 나타내는 비트는 다음과 같습니다.

int bit = 1 << (next - 1);

이미 방문한 고객인지는 비트 AND 연산으로 확인합니다.

if ((mask & bit) != 0) continue;

새로운 고객을 방문한 상태는 비트 OR 연산으로 만듭니다.

int nextMask = mask | bit;

고객이 NN명이라면 가능한 방문 상태는 총 2N2^N개입니다.

모든 고객을 방문한 상태는 하위 NN개 비트가 모두 1인 상태이므로 다음과 같이 구할 수 있습니다.

fullMask = (1 << N) - 1;

예를 들어 고객이 4명이라면 다음과 같습니다.

1 << 4        = 10000
(1 << 4) - 1  = 01111

따라서 모든 고객을 방문했는지는 다음 조건으로 확인할 수 있습니다.

if (mask == fullMask)

종료 조건

모든 고객을 방문했다면 남아 있는 이동은 현재 위치에서 집까지 가는 것뿐입니다.

if (mask == fullMask) return dist[current][home];

따라서 모든 고객을 방문한 상태에서의 최소 추가 비용은 다음과 같습니다.

DP(fullMask,current)=dist[current][home]DP(\text{fullMask}, current)=dist[current][home]

점화식

아직 방문하지 않은 고객 중 한 명을 다음 방문 대상으로 선택합니다.

현재 위치에서 다음 고객까지의 거리와, 다음 상태에서 집까지 가는 최소 비용을 더합니다.

result = Math.min(result, dist[current][next] + tsp(mask | bit, next));

점화식은 다음과 같이 표현할 수 있습니다.

DP(mask,current)=min⁡next∉mask(dist[current][next]+DP(mask∪next,next))DP(mask, current)=\min_{next \notin mask}\left(dist[current][next]+DP(mask \cup {next}, next)\right)

코드의 각 요소는 다음과 대응합니다.

mask                 → 현재까지 방문한 고객 집합
current              → 현재 위치
next                 → 다음으로 방문할 고객
dist[current][next]  → 현재 위치에서 다음 고객까지의 거리
mask | bit           → next 고객을 방문한 새로운 상태

현재 상태에서 방문 가능한 모든 다음 고객을 확인한 뒤 그중 최솟값을 저장하므로, dp[mask][current]에는 해당 상태에서의 최소 비용이 저장됩니다.

return dp[mask][current] = result;

메모이제이션

이미 계산한 상태에 다시 도달한 경우에는 해당 상태를 다시 탐색하지 않고 저장된 값을 반환합니다.

if (dp[mask][current] != -1) {
    return dp[mask][current];
}

여기서 DP가 저장하는 값은 회사에서 현재 위치까지 이동한 누적 거리가 아닙니다.

DP에는 현재 상태에서 출발하여 남은 고객을 방문하고 집까지 가는 최소 추가 비용이 저장됩니다.

서로 다른 경로가 같은 (mask, current) 상태에 도달했을 때, 지금까지의 누적 비용은 다를 수 있습니다.

하지만 현재 위치와 남은 고객 집합이 같다면 앞으로 필요한 최소 비용은 같으므로 DP 값을 재사용할 수 있습니다.

시간 복잡도

비트마스크의 가능한 상태 수는 다음과 같습니다.

2N2^N

각 방문 상태에서 현재 위치는 회사 또는 고객 중 하나가 될 수 있으므로 DP 상태 수는 대략 다음과 같습니다.

O(N×2N)O(N \times 2^N)

각 상태에서는 다음으로 방문할 고객을 최대 NN명까지 확인합니다.

따라서 전체 시간 복잡도는 다음과 같습니다.

O(N2×2N)O(N^2 \times 2^N)

DP 배열의 공간 복잡도는 다음과 같습니다.

O(N×2N)O(N \times 2^N)

DFS와 비트마스킹 DP 비교

구분순열 DFS비트마스킹 DP
방문 상태boolean[] visited정수 비트마스크
탐색 방식모든 방문 순서 탐색동일한 상태의 계산 재사용
가지치기현재 최솟값 활용메모이제이션 활용
최악 시간 복잡도O(N!)O(N!)O(N2×2N)O(N^2 \times 2^N)
공간 복잡도O(N)O(N)O(N×2N)O(N \times 2^N)
특징구현이 직관적중복 상태 계산 제거

정리

순열 DFS는 가능한 모든 고객 방문 순서를 직접 확인하는 방식입니다.

O(N!)O(N!)

현재까지 구한 최솟값을 활용한 가지치기와 거리순 탐색을 적용하면 실제 탐색량을 줄일 수 있습니다.

하지만 가지치기의 효과는 입력에 따라 달라질 수 있으므로 최악 시간 복잡도는 여전히 O(N!)O(N!)입니다.

비트마스킹 DP는 방문한 고객 집합과 현재 위치가 같은 상태의 계산 결과를 재사용합니다.

O(N2×2N)O(N^2 \times 2^N)

고객 수가 최대 10명이므로 두 방식 모두 문제를 해결할 수 있습니다.

순열 DFS는 가능한 방문 순서를 직접 탐색하고 가지치기를 적용하는 과정을 연습하기 좋습니다.

비트마스킹 DP는 방문 순서가 달라도 동일한 상태로 합쳐질 수 있다는 점을 이용해 중복 계산을 제거한다는 점에서 의미 있는 최적화 방법입니다.

코드

dfs 코드

import java.io.*;
import java.util.*;
 
class Edge implements Comparable<Edge> {
    int v;
    int w;
 
    public Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }
 
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.w, other.w);
    }
}

class Node {
	int y;
	int x;
	
	public Node (int y, int x) {
		this.y = y;
		this.x = x;
	}
}
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Edge>[] graph;
    static boolean[] visited;
    static int minDistance;
    static int home;
    static int N;
 
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            init();
 
            visited[0] = true;
 
            dfs(0, 0, 0);
 
            sb.append('#').append(t).append(' ').append(minDistance).append('\n');
        }
 
        System.out.print(sb);
    }
 
 
    static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
 
        int totalNodes = N + 2;
        home = N + 1;
 
        st = new StringTokenizer(br.readLine());
        Node[] nodes = new Node[totalNodes];
        nodes[0] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        nodes[home] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
 
        for (int i = 1; i <= N; i++) {
        	nodes[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
 
        graph = new ArrayList[totalNodes];
 
        for (int i = 0; i < totalNodes; i++) {
            graph[i] = new ArrayList<>();
        }
 
        for (int from = 0; from < totalNodes; from++) {
            for (int to = 0; to < totalNodes; to++) {
                if (from == to) {
                    continue;
                }
 
                int distance = calDist(nodes[from], nodes[to]);
                graph[from].add(new Edge(to, distance));
            }
 
            Collections.sort(graph[from]);
        }
 
        visited = new boolean[totalNodes];
        minDistance = Integer.MAX_VALUE;
    }
 
 
    static void dfs(int current, int visitedCount, int distance) {
        if (distance >= minDistance) {
            return;
        }
 
        if (visitedCount == N) {
            for (Edge edge : graph[current]) {
                if (edge.v == home) {
                    minDistance = Math.min(minDistance, distance + edge.w);
                    return;
                }
            }
        }
 
        for (Edge edge : graph[current]) {
            int next = edge.v;
 
            if (next < 1 || next > N) continue;
            if (visited[next]) continue;
 
            visited[next] = true;
            dfs(next, visitedCount + 1, distance + edge.w);
            visited[next] = false;
        }
    }
    
    static int calDist(Node from, Node to) {
    	return Math.abs(from.y - to.y) + Math.abs(from.x - to.x);
    }
}

tsp 코드

import java.util.*;
import java.io.*;
 
class Edge implements Comparable<Edge> {
    int v;
    int w;
 
    public Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }
 
    public int compareTo(Edge o) {
        return Integer.compare(this.w, o.w);
    }
}
 
class Node {
    int x;
    int y;
 
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Solution {
    static final int INF = 1000000000;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] dp;
    static int[][] dist;
    static int totalNodes;
    static int fullMask;
    static int office;
    static int home;
    static int N;
 
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            init();
            sb.append('#').append(t).append(' ').append(tsp(0, office)).append('\n');
        }
 
        System.out.print(sb);
    }
 
    static int tsp(int mask, int current) {
        if (mask == fullMask) return dist[current][home];
        if (dp[mask][current] != -1) return dp[mask][current];
 
        int result = INF;
 
        for (int next = 1; next <= N; next++) {
            if (current == next) continue;
 
            int bit = 1 << (next - 1);
            if ((mask & bit) != 0) continue;
 
            result = Math.min(result, dist[current][next] + tsp(mask | bit, next));
        }
 
        return dp[mask][current] = result;
    }
 
    static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        totalNodes = N + 2;
        office = 0;
        home = N + 1;
        fullMask = (1 << N) - 1;
 
        Node[] nodes = new Node[totalNodes];
 
        st = new StringTokenizer(br.readLine());
        nodes[office] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        nodes[home] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
 
        for (int customer = 1; customer <= N; customer++) {
            nodes[customer] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
 
        dist = new int[totalNodes][totalNodes];
        setGraph(nodes);
 
        dp = new int[1 << N][N + 1];
 
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
    }
 
    static void setGraph(Node[] nodes) {
        for (int from = 0; from < totalNodes - 1; from++) {
            for (int to = from + 1; to < totalNodes; to++) {
                int distance = calDist(nodes[from], nodes[to]);
 
                dist[from][to] = distance;
                dist[to][from] = distance;
            }
        }
    }
 
    static int calDist(Node from, Node to) {
        return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
    }
}
profile
WTS
while True: study()
이전 포스트

[SWEA 6808] 규영이와 인영이의 카드게임 - JAVA

다음 포스트

[정올 G3] 무등산 등반 - JAVA

0개의 댓글