공부 169일차: 백준 10971번 외판원 순회 2 자바 java

10971 외판원 순회 2

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

10971번: 외판원 순회 2

 

 

 

---

백준 10971번 문제 외판원 순회 2

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/312

공부 167일차: 백준 10819번 차이를 최대로 자바 java

참고하면 좋은 문제!

 

외판원이 어느 도시에서 출발하건, 모든 도시를 거쳐 다시 처음 도시로 돌아와야 한다는 것
n개의 도시가 주어진다 (인덱스로 쉽게 이해하기 위해 0번째 도시부터 n-1번째 도시까지라고 가정)

주어진 예제로 살펴보면 다음과 같다

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

0번째 도시
1번째 도시
2번째 도시
3번째 도시

여기서 순서대로 0 → 1 → 2 → 3 → 1 번째 도시를 거친다고 할 때,
W[0][1] = 10
W[1][2] = 9
W[2][3] = 12
W[3][0] = 8
로, 총 39의 비용이 든다

이런 식으로 모든 순서를 구해보고 비교해봐야 하는데,
이때 이 순서는 아래처럼 DFS 방식으로 구하면 모든 경우를 확인해볼 수 있다

W[0][1]
W[1][2]
W[2][3]
W[3][0]
 
W[0][1]
W[1][3]
W[3][2]
W[2][0]
 
W[0][2]
W[2][1]
W[1][3]
W[3][0]
 
W[0][2]
W[2][3]
W[3][1]
W[1][0]
 
...
 
W[1][0]
W[0][2]
W[2][3]
W[3][1]
 
W[1][0]
W[0][3]
W[3][2]
W[2][1]

 

 

 

---

정답 인정 코드

---

 

1)

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int min = 10_000_000;
    static int[] arr;
    static boolean[] visited;
    static int[][] W;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        n = Integer.parseInt(br.readLine());
        W = new int[n][n];
        arr = new int[n];
        visited = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        DFS(0);
        bw.write(min+"");
        bw.flush();
        bw.close();
    }
    
    public static void DFS(int depth) throws IOException{
        if(depth == n) {
            min = Math.min(getSum(), min);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = i;
                DFS(depth+1);
                visited[i] = false;
            }
        }
    }
 
    public static int getSum() {
        int sum = 0;
        for(int i = 0; i < n-1; i++) {            
            if(W[arr[i]][arr[i+1]] != 0) {
                sum += W[arr[i]][arr[i+1]];
            }else {
                sum += 10_000_000;    // 0이다 == 갈 수 없는 경로 == 최대값으로 처리하여 최소값이 될 수 없도록
            }
        }
        if(W[arr[n-1]][arr[0]] != 0) {    
            sum += W[arr[n-1]][arr[0]];
        }else {
            sum += 10_000_000;
        }
        System.out.println();
        return sum;
    }
}

 

위 방식대로 구한 코드

정답인정되긴 했지만 조금 지저분해 보인다

 

 

2) 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int min = 10_000_000;
    static int[] arr;
    static boolean[] visited;
    static int[][] W;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        n = Integer.parseInt(br.readLine());
        W = new int[n][n];
        arr = new int[n];
        visited = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        DFS(0);
        bw.write(min+"");
        bw.flush();
        bw.close();
    }
    
    public static void DFS(int depth) throws IOException{
        if(depth == n) {
            min = Math.min(getSum(), min);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = i;
                DFS(depth+1);
                visited[i] = false;
            }
        }
    }
 
    public static int getSum() {
        int sum = 0;
        for(int i = 0; i < n-1; i++) {            
            if(W[arr[i]][arr[i+1]] == 0 || W[arr[n-1]][arr[0]] == 0){
                return 10_000_001;    // 0이다 == 갈 수 없는 경로 == 최대값으로 처리하여 최소값이 될 수 없도록
            }
            sum += W[arr[i]][arr[i+1]];
        }
        sum += W[arr[n-1]][arr[0]];
        return sum;
    }
}
 

바로 return값으로 빼내는 방법도 있다

 

 

 

---

https://lotuslee.tistory.com/m/92?category=848933 

나와 다른 방법은 이 블로그를 참고하면 좋을 듯?