[백준] 10971번 - 외판원 순회 2 (!) (JAVA)

[백준] 10971번 - 외판원 순회 2 (!) (JAVA)

---

[ 접근 방법 ]

DFS를 이용하여 해결하였다.

 

* 첫번째 방법 (시간초과)

첫번째로 생각한 방법은 N X N 비용 2차원 배열에, 각 행과 열에 중복하지 않고, N개의 원소를 선택하는 방법이다.

 

* 문제에 예제 1을 그래도 사용하였다.

 

경로 : 2 -> 1

row : 2 와 col : 1 을 제외한다.

 

 

경로 : 2 -> 1 -> 3

row : 1 와 col : 3 을 제외한다.

 

 

경로 : 2 -> 1 -> 3 -> 4

row : 3 와 col : 4 을 제외한다.

 

 

경로 : 2 -> 1 -> 3 -> 4 -> 2

row : 4 와 col : 2 을 제외한다.

 

 

* 두번째 방법 (성공)

DFS 함수에 매개변수로,

경로의 출발위치는 나타내는 "start"

현재위치를 나타내는 "now"

지난 도시의 수를 나타내는 "depth"

경로의 누적 비용을 나타내는 "sum"

을 사용한다.

 

void dfs(int start, int now, int depth, int sum){
	
    // 현재 위치 == 시작점 AND 경로 누적 비용 > 0
    if(now == start AND sum > 0){
    	최솟값 갱신 (현재 누적 비용, 최솟값)
        
        return;
    }
    
    for(i : 1 -> N){
    	if(길이 존재 O){
        	
            // 모든 도시를 방문한 경우에 시작 위치로 이동가능
            if(i == start AND depth == N){
            	sum += (now -> i 이동 비용)
                dfs(start, i, depth + 1, sum)
            }
            
            else if(i에 방문하지 않음){
            	i에 방문함을 저장.
                sum += (now -> i 이동 비용)
                
                dfs(start, i, depth + 1, sum)
                
                // 복원
                sum -= (now -> i 이동 비용)
                i에 방문하지 않음을 저장.
            }
        }
    }
    
    return;
}

 

* 모든 도시를 다 방문한 다음에 시작도시로 이동할 수 있도록 별도 예외 처리

---

[ JAVA 코드 - 첫번째 방법 (시간 초과) ]

// 10971번 - 외판원 순회 2
import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[][] cost; // 경로 별 비용
    static int[] arr; // 비용 배열
    static boolean[] visit_row; // 행 방문 여부
    static boolean[] visit_col; // 열 방문 여부
    static int min = Integer.MAX_VALUE; // 최소 비용

    // 최소 비용 찾기
    public static void findMin(int depth){
        // 모든 경로 탐색
        if(depth == N){
            int sum = 0;
            for(int val : arr){
                sum += val;
            }
            min = Math.min(min, sum);
            return;
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                // 탐색하지 않은 행/열 AND 길이 존재하면 탐색
                if(!visit_row[i] && !visit_col[j] && cost[i][j] != 0){
                    visit_row[i] = true;
                    visit_col[j] = true;
                    arr[depth] = cost[i][j];
                    findMin(depth + 1);
                    visit_row[i] = false;
                    visit_col[j] = false;
                }
            }
        }

        return;
    }

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        cost = new int[N][N];
        arr = new int[N];
        visit_row = new boolean[N];
        visit_col = new boolean[N];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1. 최소 비용 구하기
        findMin(0);

        // 2. 최소 비용 출력
        bw.write(min + "\n");

        bw.flush();
        br.close();
        bw.close();      
    }
}

 

 

[ JAVA 코드 - 두번째 방법 (성공) ]

// 10971번 - 외판원 순회 2
import java.util.*;
import java.io.*;

public class Main {

    static int min = Integer.MAX_VALUE;
    static int[][] cost;
    static int N;
    static boolean[] visit;
    static int[] arr;

    public static void dfs(int start, int now, int depth, int sum){
        
        if(now == start && sum > 0){
            min = Math.min(min, sum);
            return;
        }

        for(int i=1; i<=N; i++){

            if(cost[now][i] > 0){

                if(i == start && depth == N){
                    sum += cost[now][i];
                    dfs(start, i, depth + 1, sum);    
                }

                else if(!visit[i]) {
                    visit[i] = true;
                    sum += cost[now][i];

                    dfs(start, i, depth + 1, sum);

                    sum -= cost[now][i];
                    visit[i] = false;
                }
            }
        }

        return;
    }

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        cost = 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++){
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visit[1] = true;
        dfs(1, 1, 1, 0);

        bw.write(min + "\n");
        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

1. 어려웠던 점

- 경로 끝에 출발했던 도시로 돌아오는 것을 따로 예외처리 하는 것이 어려웠다.

 

2. 알게된 점

- DFS 문제를 조금만 틀면 풀이방법을 생각하기에 매우 까다로움.

- DFS 함수에 매개변수를 좀더 적극적으로 활용해야 함.

 

3. 개선 방향

- 응용 문제를 반복하여 풀어서 숙달해야 함.