[백준] 10971번 외판원 순회2 JAVA (자바) 풀이

문제 10971번 (백트래킹)

 

 :  1번 ~ N번 도시

    한 도시에서 출발해 N개의 도시를 거쳐 원래의 도시로 돌아오는 순회 여행 경로

    (한 번 갔던 도시로는 다시 갈 수 없다)

 

 :  이동 비용 W[i][j] = 도시 i에서 도시 j로 가기 위한 비용 (W[i][j] ≠ W[j][i])

    W[i][i]는 항상 0 / 갈 수 없는 경우도 0

 

 :  가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

 

 

 [입력]

 :  첫째 줄에 도시의 수 N (2 ≤ N ≤ 10)

 :  다음 N개의 줄에는 비용 행렬 (각 행렬의 성분은 1,000,000 이하의 양의 정수)

    (갈 수 없는 경우는 0)

 [출력]

 :  순회에 필요한 최소 비용을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 조건1  이미 방문한 곳을 중복해서 방문하지 않는다

 조건2  경로가 없는 경우는 탐색하지 않는다

 조건3  모든 도시를 방문하지 않고 출발위치로 되돌아오지 않는다

 

 종료 조건)  arr[now][start]!=0   /   count==N

 count가 N이되면 끝난 것이기 때문에 종료한다

 뿐만 아니라 현 위치에서 다시 시작점 위치로 되돌아갈 때 종료가 가능하다
 now == start 로 표현해도 되지만 중요한건 시작점 위치로 돌아갈때 비용이 0 이라면 갈 수 없는 길이므로 
 배열이  0이 아님을 반드시 확인해야한다 

 

 백트래킹이 끝난 뒤에는 다시 visit을 false로 설정해 다음 경로를 이동한다

 

 키포인트)  시작지점은 고정으로 해도 된다

 처음에는 시작지점을 for문을 통해서 순차적으로 바꿔가며 백트래킹을 돌리려고 했지만

 순회는 어느 지점에서 돌던 결국 제자리로 돌아오기 때문에 시작지점을 어디로 해도 결과는 같다

 예로 도시 1에서 시작하는 1-2-3-4-1 경로든, 도시 2에서 시작하는 2-3-4-1-2 경로든 같다는 의미

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,arr[][];
    static boolean visit[];
    static int result=Integer.MAX_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        arr=new int[N+1][N+1];
        visit=new boolean[N+1];
        
        for(int i=1; i<=N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }
      
        visit[1] = true;
        back(1,1,1,0);
        System.out.println(result);
        
    }
    
    static void back(int start, int now, int count, int cost){
        if(arr[now][start]!=0 && count==N){
            result = Math.min(result,cost+arr[now][start]);
            return;
        }
        for(int next=1;next<=N;next++){
            if(arr[now][next]>0&&!visit[next]){
                visit[next]=true;
                back(start, next, count+1, cost+arr[now][next]);
                visit[next] = false;
                
            }
        }
    }
}

 

 [해설]
     

 :  static int N,arr[][];
    static boolean visit[];
    static int result=Integer.MAX_VALUE;

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N=Integer.parseInt(br.readLine());
    arr=new int[N+1][N+1];
    visit=new boolean[N+1];
        
 :  for(int i=1; i<=N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());  arr 배열 입력받기
            }
    }
      
 :  visit[1] = true;  시작지점 true로 변경 후 백트래킹 시작
    back(1,1,1,0);  시작위치 1 (고정) / 현위치 1 / count 1 / 비용은 0
    System.out.println(result);  결과 출력
      
    
 :  static void back(int start, int now, int count, int cost){  백트래킹 시작
        if(arr[now][start]!=0 && count==N){  N번의 순회 끝에 start 지점에 도착할 때 0이 아니여야 경로가 있다
            result = Math.min(result,cost+arr[now][start]);  지금까지의 비용에 현재 비용을 더해서 출력해라
            return;
        }
        for(int next=1;next<=N;next++){  
            if(arr[now][next]>0&&!visit[next]){ 경로가 존재하고 방문 전이라면 이동
                visit[next]=true;  방문처리
                back(start, next, count+1, cost+arr[now][next]);  다시 백트래킹
                visit[next] = false;  방문취소
                
            }
        }
    }

  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *