[삼성 SW 역량 테스트 기출 문제] 스타트와 링크 - 레벨2, 백트래킹

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

14889번: 스타트와 링크

 

 

이문제는 백트래킹으로 혼자 풀어냈으나 문제점은 시간초과가 발생한다는점입니다.

우선 시간초과가 걸린 코드입니다.

package Main;

import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Scanner;


public class Main {
	
	static int N;
	static int[][] arr;
	static int minvalue = Integer.MAX_VALUE;
	static boolean[] visited;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		
		arr = new int[N][N];
		visited = new boolean[N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		func(0);

		System.out.println(minvalue);
		
	}
	
	public static void func(int cnt) {
		
		if(cnt==N/2) {
			ArrayList<Integer> startteam = new ArrayList<>();
			ArrayList<Integer> linkteam = new ArrayList<>();

			for(int i=0;i<N;i++) {
				if(visited[i] == true) {
					startteam.add(i);
				}
				else {
					linkteam.add(i);
				}
			}
			
			int startteamsum =0;
			int linkteamsum = 0;
			
			for(int i=0;i<startteam.size();i++) {
				for(int j=0;j<startteam.size();j++) {
					if(i!=j) {
						startteamsum += arr[startteam.get(i)][startteam.get(j)];
					}
				}
			}

			for(int i=0;i<linkteam.size();i++) {
				for(int j=0;j<linkteam.size();j++) {
					if(i!=j) {
						linkteamsum += arr[linkteam.get(i)][linkteam.get(j)];
					}
				}
			}
			
			int diff = startteamsum - linkteamsum;
			diff = Math.abs(diff);
			minvalue = Math.min(minvalue, diff);
			return; 
		}
		
		for(int i=0;i<N;i++) {
			if(visited[i] == false) {
				visited[i] = true;
				func(cnt+1);
				visited[i] = false;
			}
		}

	}

	
}

 

 

 

 

시간초과를 해결한 코드입니다.

package Main;

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


public class Main {
	
	static int N;
	static int[][] arr;
	static int minvalue = Integer.MAX_VALUE;
	static boolean[] visited;
	
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		arr = new int[N][N];
		visited = new boolean[N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		func(0,0);

		System.out.println(minvalue);
		
	}
	
	public static void func(int start, int cnt) {
		
		if(cnt==N/2) {
			int[] startteam = new int[N/2];
			int[] linkteam = new int[N/2];
			int startteam_index = 0;
			int linkteam_index = 0;
			
			for(int i=0;i<N;i++) {
				if(visited[i] == true) {
					startteam[startteam_index++] = i;
				}
				else {
					linkteam[linkteam_index++] = i;
				}
			}
			
			int startteamsum =0;
			int linkteamsum = 0;
			
			for(int i=0;i<startteam.length;i++) {
				for(int j=i+1;j<startteam.length;j++) {
					
					startteamsum += arr[startteam[i]][startteam[j]];
					startteamsum += arr[startteam[j]][startteam[i]];
					
					linkteamsum += arr[linkteam[i]][linkteam[j]];
					linkteamsum += arr[linkteam[j]][linkteam[i]];
				}
			}

			int diff = Math.abs(startteamsum - linkteamsum);
			minvalue = Math.min(minvalue, diff);
			return; 
		}
		
		for(int i=start;i<N;i++) {
			if(visited[i] == false) {
				visited[i] = true;
				func(i, cnt+1);
				visited[i] = false;
			}
		}

	}

	
}

 

 

차이점은 func(int v, int cnt)에서 int v를 통하여

1번 2번 3번 4번을 탐색하고, 

 

2번 3번 4번을 탐색하고

 

3번 4번을 탐색하고

 

4번을 탐색하여 중복을 줄였습니다.

 

만약 func(int cnt)로 했다면

1번 2번 3번 4번

 

1번 2번 3번 4번 

 

이렇게 계속해서 실행되었을 것입니다.