[백준][JAVA]스타트와 링크(14889번) - 백트래킹 algorithm 그리고 재귀의 이해

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

14889번: 스타트와 링크

* 문제는 해당 게시물 참고바랍니다.

 

해당문제는 재귀와 백트래킹을 이용하여 동작을 구현하는 문제입니다.

 

백트래킹이란 해를 찾는 도중 아니다 싶으면 더 이상 깊이 들어가지 않고, 이전 단계로 돌아가 해를 찾아나가는 기법입니다. 모든 경우의 수를 탐색하는 브루트 포스 algorithm과는 다르게 문제를 최적화하여 비교적 빠르게 풀어나갈 수 있습니다. 

요약하자면 

브루트 포스 - 모든 가지에 다 가봄

백트래킹 - 가지치기를 통해 불필요한 가지에는 가지 않습니다.

 

이제 해당 문제를 해결한 코드에  대해 설명하겠습니다.

우선 전체 코드입니다.

import java.util.*;
public class Main {

    static int n;
    static boolean[] team;
    static int[][] array;

    static int Min_value = Integer.MAX_VALUE;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        team = new boolean[n];
        array = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                array[i][j] = scanner.nextInt();
            }
        }

        synergy(0,0);
        System.out.println(Min_value);

    }
    static void synergy(int idx, int count){
        if(count == n/2){
            synergy_sum();
            return;
        }
        for(int i=idx; i<n; i++){
            if(team[i] == false){
                team[i] = true;
                synergy(i+1,count+1);
                team[i] = false;
            }
        }

    }

    static void synergy_sum(){
        int start_team = 0;
        int link_team = 0;

        for(int i=0; i<n-1; i++){
             for(int k=i+1; k<n; k++){
                 if(team[i]==true && team[k]==true){
                     start_team += array[i][k];
                     start_team += array[k][i];
                 } else if(team[i]==false && team[k]==false){
                     link_team += array[i][k];
                     link_team += array[k][i];
                 }
             }
         }
        int result = Math.abs(start_team-link_team);


        if(result == 0){
            System.out.println(result);
            System.exit(0);
        } else {
            Min_value = Math.min(result, Min_value);
        }
    }
}

 

여기서 boolean 배열의 특징으로는 최초의 경우 false로 값이 초기화되어 있습니다.

static boolean[] team;

 

결과

 

 

개인적으로 저는 아직 재귀가 햇갈려서 재귀에 대해 조금 더 이야기 하겠습니다.

 

재귀에 반복문을 함께 사용했을 때 구조파악을 위해 해당 코드를 사용했었습니다.

    static void recursive(int idx, int count){
        System.out.println("재귀시작");
        if(count == n/2){
            for(int i=0; i<n; i++){
                System.out.printf("[%b]",b[i]);
            }
            System.out.println("1cycle");
            return;
        }
        for(int i=idx; i<n; i++){
            if(!b[i]){
                b[i] = true;
                recursive(i+1, count +1);
                System.out.println("재귀중");
                b[i]=false;

            }
        }
    }

해당 코드를 돌려 로그창을 보시면 

이런 느낌으로 진행됩니다.