[백준 2098] - 외판원 순회(JAVA)[골드1]

문제

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

문제 풀이

외판원 문제는 유명한 알고리즘 문제이다.

TSP라고 하는데, 해당 문제를 풀기 위해서 DP나 Branch & Bound 알고리즘이 사용된다.

처음에는 임의의 출발점에 대해서 모든 최단거리를 구하려고 했지만, 규칙을 발견했다.

1->2->3->4->5->1와 2->3->4->5->1->2의 값이 같다는 사실이다.

이유는 항상 마지막 지점에서 출발지점으로 되돌아가야하기 때문이다.

이는 해밀턴 경로의 개념과 연관이 있는데, 임의의 사이클에 대해서 출발지점이 다르더라도, 경로가 같다면 동일한 취급을 하기 때문이다.

따라서 우리는 출발지점에 대해서 결정해줄 필요 없이 출발점을 고정시켜서 경로를 구하고, 그 경로에 대한 값을 구하면 된다.

처음 문제를 봤을때 감이 잡히지 않아서 알고리즘 분류를 봤고, 비트마스킹이란 개념이 나왔다.

알고리즘에서 비트마스킹을 이용할 때 흔히 스위치의 on, off의 개념을 사용하기 위해서 사용한다는 것은 미리 알고 있었고,

비트 마스킹을 통해서 내가 방문한 경로를 저장하고, 방문한 도시에 대한 필터링을 할 수 있을 것이라고 생각했다.

만약 비트 마스킹을 쓰지 않았다면 Union & Find or visit 배열을 통해서 방문의 여부를 판단했을 것이다.

하지만 문제에서 비트마스킹을 강조한 만큼 위 방법을 쓰면 시간초과가 나올 것이라는 사실은 당연하다.

위에서 출발점에 대해서 신경 쓸 필요가 없기 때문에 출발점을 1로 고정시켰다(코드상으로는 0번 정점이다)

만약 0번->1번을 방문할 경우 1번에 대한 방문여부를 검사해야 한다.

만약 비트마스킹을 쓰지 않았다면 visit [1]를 검사하거나, union&find를 통해서 0의 부모와 1의 부모가 같은지 판단을 해야 하지만

비트마스킹을 쓴다면 간단하게 해결할 수 있다.

 

방문 여부 검사하기

(visited & 1<<1)>=1)

visited는 내가 방문한 도시들의 상태를 저장하는 값이다.

1번 도시를 방문했다면 visited는 xxxxx11이 될 것이다.

순수하게 1번 도시의 방문 여부를 판단하기 위해서 1을 1번 왼쪽으로 시프트 하면 10이 된다.

만약 두 값을 & 연산해서 1이라면 visited는 1번을 방문했다는 뜻이다.

한 번의 예를 더 들어서

현재 visited는 xxxx011일 때,

2번 도시 방문 여부를 판단하기 위해서는

1을 2번 왼쪽으로 시프트 연산해서 100이라는 값과 visited를 & 연산을 하고,

결괏값은 0이 된다. 0이라는 뜻은 2번 도시를 방문하지 않았다는 뜻이다.

이렇게 비트마스킹을 통해서 i번째 도시를 판단했는지를 검사할 수 있다.

만약 방문하지 않았다면 방문했다는 표시는 어떻게 해야 할까?

 

방문 표시하기

visited | 1 << i

or 연산을 통해서 할 수 있다.

즉 xxxx011과 100을 or 연산해서 xxxx111이라는 visited값을 만들어주는 것이다.

탐색의 끝은 어떻게 판단할 수 있을까?

만약 4개의 도시가 있을 경우 4개를 전부 방문했을 경우 visited는 1111이 될 것이다. 이는 2^4 -1의 결괏값과 동일하다.

종료 조건

visitied == (1<<n)-1

두 값이 같을 경우 모든 도시를 방문한 것이다.

이렇게 모든 도시를 방문할 경우 우리는 마지막 도시에서 출발도시(0)로 갈 수 있는지 검사를 해줘야 한다.

코드의 흐름은 이러하고, 자세한 내용은 전체 코드를 통해서 확인하면 될 것이다.

전체 코드

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static int[][] dp;

    static final int INF = 999999999;


    static int[][] graph = new int[16][16];

    public static void main(String[] args) throws IOException {
        input();
        System.out.print(tsp(0, 1)); //0번부터 탐색 시작
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        dp = new int[16][(1 << n)];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < (1 << n); j++) {
                dp[i][j] = -1;
            }
        }
    }

    public static int tsp(int now, int visited) {
        if (visited == (1 << n) - 1) { //전부다 돌았을때
            if (graph[now][0] == 0) { //출발지점으로 못돌아갈 경우
                return INF;
            }
            return graph[now][0];
        }
        if (dp[now][visited] != -1) return dp[now][visited]; //이미 값이 있는 경우 그대로 리턴함.
        dp[now][visited] = INF;
        for (int i = 0; i < n; i++) {
            if (graph[now][i] == 0) //경로가 없을 경우
                continue;
            if ((visited & 1 << i) >= 1) //visit가 i번지를 방문했는지 검사를 함
                continue;
            int next = 1 << i;
            dp[now][visited] = Math.min(dp[now][visited], graph[now][i] + tsp(i, visited | next));
        }
        return dp[now][visited];
    }
}