[백준] 15661번: 링크와 스타트

문제

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

문제는 꽤나 간단하다.
N명이 모여서 축구를 하려고 한다.
두 팀으로 나눌건데 각 팀의 인원수는 다를 수 있으나 한 명 이상이 무조건 있어야 한다. (한 명도 없는 그룹은 없음)
그렇게 해서 팀으로 나누고 팀의 능력치를 구하고자 한다.
팀의 능력치는 해당 팀에 속한 사람들의 쌍에 의해 결정된다.
만약 5명이 있다고 할 때 A team에 1,3번 B team에 2, 4, 5번이 배치가 된다고 하자.
그러면 A 팀의 능력치는 P(1, 3) + P(3, 1)이고 B 팀의 능력치는 P(2, 4) + P(2, 5) + P(4, 2) + P(4, 5) + P(5, 2) + P(5, 4)이다.
여기서 주의할 점!! P(1, 3) != P(3, 1)이다.

해당 능력치를 모두 계산해서 team A와 team B의 능력치가 가장 적게 차이나는 값을 반환해주면 된다.

알고리즘

제일 처음 헷갈린 것은 team을 나누는 경우의 수가 무한히 많은데 이를 어떻게 해결할까?
이는 boolean 배열로 해결할 수 있다.
팀은 A 또는 B이기 때문에 0이면 A, 1이면 B라는 식으로 배정하면서 진행하면 된다.
또한 백트래킹을 사용해서 각 사용자들의 팀을 계속 바꾸어 가면서 비교하면 된다.
여기서 주의해야 할 것은 각 팀에 무조건 1명은 있어야 한다는 것

++ 1, 3이 team A에 배정, 2, 4, 5가 team B에 배정되는 것과 2, 4, 5가 team A에 배정, 1, 3이 team A에 배정되는 것은 같은 값을 반환한다.

코드

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

public class Baekjoon15661 {
	public static int board[][];
	public static int N;
	public static int min = Integer.MAX_VALUE;
	public static boolean[] selected; // team A와 B로 구분하는 배열 (0이면 A 1이면 B)

	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		selected = new boolean[N];
		
		for (int i=0 ; i<N ; i++) {
			String str[] = br.readLine().split(" ");
			for (int j=0 ; j<N ; j++) {
				board[i][j] = Integer.parseInt(str[j]);
				
			}
		}
		
		team(0, 0);
		System.out.println(min);
		
	}
	
	// 팀을 나누는 함수, count는 team A에 있는 사람의 수
	public static void team(int idx, int count) {
		// 한 팀에 1명 이상이 있을 때에만 연산 실행
		if(count >= 1 && count <= N-1) {
			calc();
		}
		
		// 마지막 사람까지 다 돌아본 경우에 종료
		if (idx == N) return;
		
		// 해당 index의 사람을 team A로 배정
		selected[idx] = true;
		team(idx + 1, count + 1);
		
		// 위에 재귀함수가 모두 종료된 후 이번에는 team B로 배정
		selected[idx] = false;
		team(idx + 1, count);
	}
	
	// 차의 값이 가장 작은 것을 계산하는 함수
	public static void calc() {
		int teamA = 0, teamB = 0;
		
		for (int i=0 ; i<N ; i++) {
			for (int j=i+1 ; j<N ; j++) {
				// i와 j의 팀이 A로 동일하면 해당 능력치를 더함
				if (selected[i] && selected[j])
					teamA += board[i][j] + board[j][i];
				// i와 j의 팀이 B로 동일하면 해당 능력치를 더함
				else if (!selected[i] && !selected[j])
					teamB += board[i][j] + board[j][i];
				// 둘의 팀이 다른 경우는 고려하지 않음
			}
		}
		min = Math.min(min, Math.abs(teamA - teamB));
	}

}

마무리

처음에는 재귀함수 진짜 못했는데 이제 점점 감을 찾아가고 있는 것 같다.
백트래킹을 사용해서 다수의 경우의 수를 해결하자