알고리즘 풀이 - 백준 10971(외판원 순회 2, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조
백트래킹 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

1~N까지의 도시 간 이동 비용이 NxN으로 주어질 때, 모든 도시를 순회하는 비용 중 가장 적은 비용으로 순회하는 경우의 비용을 구한다.(비용은 비대칭적, 1→2로 갈 때와, 2→1로 갈 때의 비용은 다를 수 있다.)

 

2. 풀이

 

유명한 TPS(외판원 순회) 문제이다. 이 문제는 풀 수 있는 방법이 다양하다.

 

 

① 완전 탐색 + 백트래킹 사용법

DP를 이용하는 것과 큰 차이는 없다고 보는데, 기본적으로 모든 도시를 탐색을 하는 방법이다. 그러나 이미 방문한 경우와 갈 수 없는 경우 및 이전 방문으로 계산된 최소 비용을 넘어서는 경우를 제외하고 탐색한다.

즉, 백트래킹을 이용해 가지치기(Pruning)을 하여 필요한 경우에만 건너서 도시를 탐색하는 방법이다.

 

② 완전 탐색 - 순열 사용법

1~N까지의 도시가 주어지기 때문에, 각 도시를 순회하는 방법을 순열로 만들어보는 것이다. 순열로 만들고 그 순열의 순서대로 해당 순회가 가능한 방법인지를 체크하고 기존의 최소 비용을 넘어서지 않는 경우에만 지속 탐색을 수행하는 방법이다.

하지만 이 방법은 순열을 사용하는 공부를 위해서는 쓸만 하겠지만 시간 복잡도는 오히려 느릴 수 있다. (순열을 구해야 하기 때문)

순열은 최초 순열에서 시작해서 다음 순열을 구해가며 진행하면 된다. 다음 순열을 구하는 방법은 상단의 링크(완전 탐색)을 클릭하거나 아래의 더보기를 클릭 후 내용을 참고한다.

※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.

아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.

1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
  → 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
      A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.

2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
  → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

3. A[i-1]과 A[j]를 Swap한다.
   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 6, 5, 3, 1}

4. i이후의 순열을 모두 뒤집는다.
   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 1, 3, 5, 6}

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 완전 탐색 + 백트래킹 해결 코드

import java.io.*;

public class Main{
    static int n;
    static int W[][];
    static int visit_cnt = 0;
    static boolean visited[];
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 주어진 값을 읽어서 변수에 저장하는 부분
        n = Integer.parseInt(br.readLine());
        W = new int[n][n];
        visited = new boolean[n];
        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                W[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        // 최초에 어디를 방문하든 전체를 방문해야 하므로, 0에서 무조건 시작한다고 가정하자.
        visited[0] = true;
        visit_cnt += 1;
        backTrack(0, 0, 0);

        bw.write(String.valueOf(min));
        bw.flush();
        br.close();
    }
    
    private static void backTrack(int cost, int start, int current){
        if(visit_cnt == n && W[current][start] != 0){
            // 현재 기존 최소값과 순회 완료 후 다시 최초로 돌아가는 경우를 비교한다.
            min = Math.min(min, cost + W[current][start]);
            return;
        }
        
        for(int i=0; i < n; i++){
            // 이미 방문이 완료되었거나 갈 수 없는 곳이면 넘어간다.
            if(visited[i] || W[current][i] == 0) continue;
            
            // 순회 종료가 안되었는데도 이미 현재 최소값을 넘어간다면 넘어간다.
            if(cost+W[current][i] > min) continue;
            visited[i] = true;
            visit_cnt += 1;
            
            backTrack(cost+W[current][i], start, i);
            
            visit_cnt -= 1;
            visited[i] = false;
        }
    }
}

 

② 완전 탐색 - 순열 해결 코드

import java.io.*;

public class Main{
    static int n;
    static int perm[];
    static int W[][];
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 주어진 값을 읽어서 변수에 저장하는 부분
        n = Integer.parseInt(br.readLine());
        perm = new int[n];
        W = new int[n][n];
        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                W[i][j] = Integer.parseInt(line[j]);
            }
            // 순열은 0부터 넣으면 순서가 원하는 대로 안될 수 있으니 1부터 넣는다.
            perm[i] = i+1;
        }
        
        while(true){
            traverse();
            boolean isNext = getNext();
            if(!isNext) break;
            
            // 어차피 원으로 순회하는 방식이므로, 순열 중에서도 앞자리를 고정시킨 상태에서만
            // 계산하면 중복 계산은 피할 수 있게 된다.
            if(perm[0] != 1) break;
        }
        
        bw.write(String.valueOf(min));
        bw.flush();
        br.close();
    }

    // 다음 순열을 구하는 메소드
    private static boolean getNext(){
        int i = n-1;
        while(i > 0 && perm[i-1] >= perm[i]) i--;
        if(i <= 0) return false;
        
        int j = i-1;
        while(j < n-1 && perm[j+1] > perm[i-1]) j++;
        swap(i-1, j);
        
        j = n-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }
    
    private static void swap(int i, int j){
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
    
    private static void traverse(){
        int cost = 0;
        int current = 0; int next = 0; int c = 0;
        
        for(int i=0; i < n-1; i++){
            // 순열의 값은 0이 아닌 1부터 넣었으니 1씩 빼주어야 한다.
            current = perm[i]-1;
            next = perm[i+1]-1;
            c = W[current][next];
            
            // 만약 갈 수 없는 경우라면 계산하지 않는다.
            if(c == 0){
                return;
            }
            cost += c;
            
            // 비용을 구하는 중 기존 min 값보다 이미 넘어섰다면 더 체크할 필요 없이 반환
            if(min < cost) return;
        }
        current = perm[n-1]-1;
        next = perm[0]-1;
        c = W[current][next];
        if(c == 0) return;
        cost += c;
        
        min = Math.min(min, cost);
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.