백준 10971(JAVA)

문제

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

10971번: 외판원 순회 2

풀이

백트래킹 문제이다.
재귀함수를 통해서 탐색하되, 가지치기를 통해 경우의 수를 줄여야한다.
재귀함수에대한 이해가 부족하면 풀기어렵다.(백트래킹 기본 N, M문제를 많이 풀어봐야한다 생각함!!)

2차원 배열로 어떠한 도시에서 어떠한 도시로가는 비용이 적혀있다.

외판원이 어떠한 도시에서 출발하여 모든 도시를 돌고 다시 시작한 어떠한 도시로 돌아오는데 최소 비용을 구하라는 것이 문제이다.
즉, 시작지점이 어떠한 도시라고 되어있으므로 어떤 도시부터 시작할지 모른다.

3 * 3 행렬을 index기준에서 살펴보면

(0, 0) (0, 1) (0, 2)

(1, 0) (1, 1) (1, 2)

(2, 0) (2, 1) (2, 2)

이다!

처음 시작하는 도시아니면 한번만 방문해야한다.
포인트는 행렬의 행(row)은 n번도시가 모든도시로 가는 모든 비용이 나타나있다는걸 아는것이다.
어떻게 일단 탐색해야하는지 생각하면

1) 먼저 0번도시에서 1번도시로 간다고 생각해보자(0 -> 0도시의 비용은 0이므로 갈수없다.)

     탐색

(0, 0) (0, 1) (0, 2)

(1, 0) (1, 1) (1, 2)

(2, 0) (2, 1) (2, 2)

이렇게 탐색하겠따. 0번도시를 거쳤으니 방문처리를 해주겠다.

2) (0, 1)에서 두번재 원소는 목표인 도시 번호를 나타내므로 1번 행을 보면된다!

그럼 1번도시에서 갈수있는 도시는 0번도시는 이미 방문처리했고, 1 -> 1은 비용이 1이므로 갈수없으므로 (1, 2)인 1 -> 2밖에없다.

     탐색

(0, 0) (0, 1) (0, 2)
탐색
(1, 0) (1, 1) (1, 2)

(2, 0) (2, 1) (2, 2)

(1, 2)를 탐색한다.

3) (1, 2)에서 두번째 원소인 2번으로 간다. 즉, (2, ~)으로 시작하는 행을 탐색하면된다.
0, 1번도시는 방문처리가 되어있고 2 -> 2는 비용이 0이므로 갈수없으니 이러한 경우만 따로 생각해서 계산해주면된다.

시작도시인 0 으로 갈수있으면(원소값이 0이아니면) 경로최소값을 업데이트하면 되고 그렇지않으면 재귀함수를 계속 돌려주면 된다.

        탐색

(0, 0) (0, 1) (0, 2)
탐색
(1, 0) (1, 1) (1, 2)
탐색
(2, 0) (2, 1) (2, 2)

나는 이런식으로 마지막 도시에서는 따로 처리를 해주었다.

이러한 일련의 한번의 탐색이 끝나면?

call stack에 쌓인 맨위의 재귀함수가 끝나면서 다시 탐색해야한다.
(이 부분은 N, M 문제를 많이 풀어보면 알수있다.)

주의할점은 시작지점을 0 ~ N - 1까지 모두 확인해봐야한다는 것이다. 시작 도시가 정해진것이 아니므로

많이 어려워 보이는데 천천히 풀면 어렵지 않은문제이다! 겁먹지말고 백트래킹에대한 기초가 탄탄하면 충분히 이해할수 있는 문제같다.

코드

package training.backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main10971 {
    static int N;
    static int[][] board;
    static int min = Integer.MAX_VALUE;
    static boolean[] visited;
    static int start;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < N; i++){
            visited = new boolean[N];
            start = i; // 시작하는 
            recursive(i, 0, 0); //i : 시작하는 도시 번호
        }

        System.out.println(min);
    }
    static void recursive(int n, int m, int subSum){
        if(m == N){
            min = Math.min(min, subSum);
            return;
        }

        for(int i = 0; i < N; i++){
            // 이건 마지막 도시에 탐색했을때 처음 도시까지의 비용을 계산하기 위한 if 문이다. 그 용도만으로 사용됨.
            if(m == N - 1 && start == i && board[n][i] != 0)
                recursive(i, m + 1, subSum + board[n][i]); // 계속해서 시작하는 도시는 업데이트해줘야함 (0, 1) 을 탐색했으면 1로 업데이트해야함
            else if(!visited[i] && board[n][i] != 0){
                visited[n] = true;
                recursive(i, m + 1, subSum + board[n][i]);  // 계속해서 시작하는 도시는 업데이트해줘야함 (0, 1) 을 탐색했으면 1로 업데이트해야함
                visited[n] = false; //탐색이 끝난 도시는 방문처리 다시 초기화해야한다.
            }
        }
    }
}

다시 풀며 느낀점

시작하는 번호를 지정해주는 것이 아닌, N, M백트래킹처럼 코드를 구현하다, 인접한 마을끼리 가는 경로 비용이 0이면 가지치기를 해주면 더 코드가 깔끔해진다.

수정한 코드

package baekjoon.백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main10971_r {
    static int N;
    static int[][] board;
    static boolean[] visited;
    static int[] result;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        board = new int[N][N];
        visited = new boolean[N];
        result = new int[N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recursive(0);
        System.out.println(min);

    }
    static void recursive(int m){
        if(m == N){
            StringBuilder sb = new StringBuilder();
            int sum = 0;

            for(int i = 0; i < N - 1; i++){
                sum += board[result[i]][result[i + 1]];
            }
            sum += board[result[N - 1]][result[0]];
            min = Math.min(sum, min);

            return;
        }
        for(int i = 0; i < N; i++){
            if(m > 0 && board[result[m - 1]][i] == 0){
                continue;
            }
            if(m == N - 1 && board[i][result[0]] == 0){
                continue;
            }
            if(!visited[i]){
                visited[i] = true;
                result[m] = i;
                recursive(m + 1);
                visited[i] = false;
            }
        }
    }
}

• for문 에서 if조건문을 통해 가지치기를 하는 것이 핵쉼!!!