[JAVA] 스타트와 링크 - DFS

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

14889번: 스타트와 링크

생각과정

- 팀원이 추가될 때마다 기존 팀원들과 추가된 팀원 상호간 더해지는 능력치를 추가

- 팀 구성이 완료되면 능력치 차이 최솟값 구하기 (dfs)

 

구현

package baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class b14889 {
	public int minA = Integer.MAX_VALUE;
	
	public void b14889(int n, int[][]ary, ArrayList<Integer> t1, ArrayList<Integer> t2, int T1ability, int T2ability, int person) {
		if(person==n) {
			//System.out.println("T1: " + T1ability + " T2: " + T2ability);
			minA = Math.min(minA, Math.abs(T1ability - T2ability));
			return;
		}
		
		ArrayList<Integer>T1 = new ArrayList();
		ArrayList<Integer>T2 = new ArrayList();

		T1.addAll(t1);
		T2.addAll(t2);
		
		boolean changedT1 = false;
		int newAbility = T1ability;
		if(T1.size()< n/2) {
			//능력치 추가
			for(int i=0;i<T1.size();i++) {
				newAbility += ary[T1.get(i)][person];
				newAbility += ary[person][T1.get(i)];
			}
			//T1에 추가
			T1.add(person);
			changedT1 = true;
			b14889(n, ary, T1, T2, newAbility, T2ability, person+1);
		}
		
		//초기화
		newAbility = T2ability;
		if(T1.size()>0 && changedT1 ==true)
			T1.remove(T1.size()-1);
		
		if(T2.size()< n/2) {
			//능력치 추가
			for(int i=0;i<T2.size();i++) {
				newAbility += ary[T2.get(i)][person];
				newAbility += ary[person][T2.get(i)];
			}
			//T2에 추가
			T2.add(person);
			b14889(n, ary, T1, T2, T1ability, newAbility, person+1);
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int [][]ary = new int[n][n];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				ary[i][j] = s.nextInt();
			}
		}
		
		ArrayList<Integer> t1 = new ArrayList();
		ArrayList<Integer> t2 = new ArrayList();
		
		b14889 b = new b14889();
		b.b14889(n, ary, t1, t2, 0, 0, 0);
		
		System.out.println(b.minA);
	}

}

 

Result

팀원 수가 고정임에도 배열 안쓰고 ArrayList 써서 그런지 메모리가 엄청 많이 쓰였다ㄷㄷ

 

 

ArrayList deep copy하는 법

ArrayList A와 ArrayList B가 있을 때, A = B라고 하면 A가 B와 같은 주소를 참조하기 때문에 A를 수정하면 B도 수정된다. 이때, A.addAll(B)를 사용하면 B의 요소 전체를 A에 더하기 때문에 Deep copy를 할 수 있다. 메모리/시간을 엄청 잡아먹으니 주의..

 

참고

https://library1008.tistory.com/47

ArrayList 깊은 복사(deep copy) vs 얕은 복사(shallow copy)

https://snoop-study.tistory.com/2

[JAVA] 완주하지 못한 선수 - ArrayList