[백트래킹] 백준 - 스타트와 링크

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

14889번: 스타트와 링크

 

-문제해설

1. 먼저 변수는 아래와 같고, 모두 전역변수이다.

n: 그래프의 크기

arr[][]: 각 선수들 조합에 따른 팀의 능력치들을 담을 2차원 배열

visit[]: 특정 선수가 팀에 배정됐음을 나타내는 방문배열 1차원배열

ans: 최종 정답값

 

2. arr에 팀의 능력치값들을 입력받는다.

 

3. cal( int index, int depth ) 메서드를 호출한다.

매개변수인 index는 팀 번호를 의미하고 depth는 재귀호출한 횟수를 의미한다.

 

먼저 n=4인 경우를 살펴보면

if( depth == (n/2) )인 경우 2개의 팀이 정해졌다는 것이므로 각 팀의 능력치합 차이를 ans에 저장해줘야한다.

이를 위해 t1은 팀1의 능력치합, t2는 팀2의 능력치합이고

 

이중 포문을 통해 

for( int i=0; i<n; i++ )

    for( int j=i+1; j<n; j++ )

 

visit[i]와 visit[j]가 1인 경우에는 

t1 += arr[i][j];

t1 += arr[j][i];

 

visit[i]와 visit[j]가 0인 경우에는

t2 += arr[i][j];

t2 += arr[j][i];

를 더해준다.

 

그리고 cha = abs( t1-t2 )의 절댓값을 확인하고

cha가 0이면 이보다 더 작은 차이는 없으므로 0을 출력하고 바로 프로그램을 종료한다.

 

0이 아니라면 기존의 최소값인 ans와 cha를 비교해서 더 작은 값으로 ans를 초기화해준다.

 

 

depth == (n/2) 이 아닌경우

4개의 팀중에서 2개의 팀을 나누기위해 아래 코드를 실행한다.

0부터 n-1인 3까지 순회하고 방문처리가 안되어있는 팀이라면 방문처리해주고 

cal( i+1, depth+1 )로 재귀호출해준다. 그리고 재귀호출하다가 depth == (n/2)가 되면 위의 과정을 반복하고 return해준다.

return으로 백트래킹한 경우 다시 visit[i] = 0을 통해 미방문처리해준다.

 

 

for( int i=0; i<n-1; i++ )

    if( visit[i] == 0 ) {

        visit[i] = 1

        cal( i+1, depth+1 )

        visit[i] = 0

    }

}

 

 

 

 

-자바

package bruteforce;

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

public class BJ14889 {
	static int n;
	static int[][] arr;
	static int[] visit;
	static int ans = Integer.MAX_VALUE;
	
	public static void cal( int index, int depth ) {
		if( depth == (n/2) ) {
			int t1 = 0;
			int t2 = 0;
			
			for( int i=0; i<n; i++ ) {
				for( int j=i+1; j<n; j++ ) {
					if( visit[i]==1 && visit[j]==1 ) {
						t1 += arr[i][j];
						t1 += arr[j][i];
					} else if( visit[i]==0 && visit[j]==0 ) {
						t2 += arr[i][j];
						t2 += arr[j][i];
					}
				}
			}
			
			//두 팀의 차이값
			int cha = Math.abs( t1-t2 );
			
			if( cha == 0 ) {
				System.out.println( cha );
				System.exit(0);
			}
			
			ans = Math.min( ans, cha );
			return;
		}
		
		for( int i=index; i<n-1; i++ ) {
			if( visit[i] == 0 ) {
				visit[i] = 1;
				cal( i+1, depth+1 );
				visit[i] = 0;
			}
		}
		
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		arr = new int[n][n];
		visit = new int[n];
		StringTokenizer st;
		for( int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j=0; j<n; j++ ) {
				arr[i][j] = Integer.parseInt( st.nextToken() );
			}
		}
		cal( 0, 0 );
		System.out.println( ans );
	}
}

 

-파이썬

from sys import stdin
def cal( index, depth ):
    global n, arr, visit, ans
    if depth == (n//2):
        t1 = 0; t2 = 0
        for i in range( n ):
            for j in range( i+1, n ):
                if visit[i] and visit[j]:
                    t1 += arr[i][j]
                    t1 += arr[j][i]
                elif visit[i]==False and visit[j]==False:
                    t2 += arr[i][j]
                    t2 += arr[j][i]
        
        cha = abs( t1-t2 )
        if cha == 0:
            print( cha )
            exit()
        
        ans = min( [ans, cha] )
        return
    
    for i in range( index, n-1 ):
        if not visit[i]:
            visit[i] = True
            cal( i+1, depth+1 )
            visit[i] = False

input = stdin.readline
n = int(input())
arr = []
for _ in range( n ):
    arr.append( list( map(int, input().split()) ) )

visit = [False] * n
ans = 9999
cal( 0, 0 )
print( ans )