백준 JAVA 10971 외판원 순회 2 리뷰

문제풀이

어느 정점에서 시작하든 최소비용은 같다. 그렇기 때문에 0 도시부터 시작했다.

예를 들어 경로가 0->1->2->3->0 이다. (다시 처음으로 돌아와야하기 때문에 0을 마지막에 추가한다.

1.  0->1->2->3->0 이거나 

2.  2->3->0->1->2 이거나

3.  3->0->1->2->3 이 비용이 결국 같다. 사이클이 형성되어있으니까 어디서 시작하든 같기 때문이다.

 

왜 dfs를 사용해야하나?

처음에 최단거리 문제라고 생각해서 bfs만 생각했다. bfs가 최단거리 구하는데 유리하다고 생각해서 bfs만 가능한 줄 알았는데 dfs라고 최단거리를 못구하는 것이 아니었다. 다만 bfs와 달리 처음 찾은 길이 최단이 아닐 수도 있기 때문에 bfs보다 속도가 느린 것이었다.

그리고 처음을 제외하고 같은 도시를 가면 안되고 각 경로마다 특징을 저장해야하기때문이라고 생각해서 dfs를 사용했다. 도시 순서를 따져야 하는 상황에서 너비 우선보다 깊이 우선탐색이 더 적절하다고 생각했다. 어떻게 보면 순열 문제로 볼 수 있기 때문에 순열에 쓰는 dfs를 사용해야한다고도 볼 수 있었다. 내가 구현한 것은 순열로 푼게 아니긴하지만 순열을 dfs로 구현해서 문제를 푼 블로그도 있었다.

그동안 인접행렬 bfs/dfs 문제는 무조건 dirX, dirY 만들어서 영역을 벗어나지 못하게 했는데 이 문제는 그런거 없이도 탐색할 수 있어서 이런식으로 출제되는 구나 알았다.

 

0도시부터 시작해서 방문하지 않은 도시들을 방문하고 비용을 추가한다. 그리고 모든 도시를 방문했으면 처음 도시로 돌아와야하는데 visited에 이미 방문처리가 되어 못온다. 그래서 allVisited 함수를 만들어서 visited 배열이 모두 true일 경우 최소비용을 계산하고 갱신하도록 만들었다.

 

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

public class Main {
    static int[][] city;
    static boolean[] visited;
    static int N;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        city=new int[N][N];
        visited=new boolean[N]; //도시 방문 여부 체크

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                city[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        visited[0]=true;
        dfs(0,0);
        System.out.println(ans);
    }
    static void dfs(int now, int cost){
        //도시를 다 탐방하면 다시 처음 도시로 돌아와야함
        if(allVisited()){
            if(city[now][0]>0){ //처음 도시로 갈수있으면
                ans=Math.min(ans,cost+city[now][0]); //최소비용 갱신
            }
        }
        for(int i=1; i<N;i++){ //다음 도시 탐색
            if(!visited[i]&&city[now][i]>0){
                visited[i]=true;
                dfs(i,cost+city[now][i]);
                //경로 다 탐색했으면 visited[i]=false 해서 다른 경로도 구할 수 있어야함
                visited[i]=false;
            }
        }
    }
    static boolean allVisited(){
        for(int i=0; i<N; i++){
            if(!visited[i]){
                return false;
            }
        }
        return true;
    }

}

 

출처1

출처2