[백준_14889번] 스타트와 링크_삼성 SW 역량테스트

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

14889번: 스타트와 링크

[문제]

 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

 BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

 

N=4이고, S가 아래와 같은 경우를 살펴보자.

i/j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

 

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

 

 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

[입력 조건]

 첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

[코드]

import java.util.Scanner;

public class BaekJoon_14889 {
	static int n;
	static int team[][]; // 점수표
	static boolean visit[]; // 방문 여부
	static int min=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		team=new int[n][n];
		visit=new boolean[n];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++)
				team[i][j]=sc.nextInt();
		}
		dfs(0,0);
		System.out.println(min);	
	}
	// idx는 인덱스, count는 조합 개수(=재귀 깊이)
	public static void dfs(int idx, int depth) {
		// 팀 조합이 완성될 경우
		if(depth==n/2) {
			/*
			 방문한 팀과 방문하지 않은 팀을 각각 나누어
			 각 팀의 점수를 구한 뒤 최솟값을 찾는다.
			*/
			score();
			return;
		}
		
		for(int i=idx;i<n;i++) {
			if(!visit[i]) {
				/*
				 * 팀을 구성하는 방법
				 * 예를 들어 n이 4일 경우 진행하면, 처음에는 1번 사람이 true가 된다. 
				 * 이후 depth를 1 증가시킨후 재귀호출을 하면 이에 의해 다음에는 2번 사람이 true가 된다.
				 * 이때는 depth가 n/2와 같아지기 때문에 true인 1,2번이 스타트 팀, 3,4번이 링크팀이 된다.
				 * score() 함수를 호출하고 return 되면 2번 사람이 false로 바뀌고 for문에 의해 3번 사람이
				 * true 값을 가지게 된다. 이후에는 앞의 과정 반복...  
				 */
				visit[i]=true;
				dfs(i+1,depth+1);
				visit[i]=false;
			}
		}
	}
	
	// 두 팀의 능력치를 계산하는 함수
	public static void score() {
		int team_start=0;
		int team_link=0;
		
		/*
		 * 대각선에는 능력치가 없기 때문에 i는 n-1까지
		 * (1,2)나 (2,1)은 같은 사람이 뽑힌 것이기 때문에 
		 * 중복을 최소화 하기 위해 j의 조건은 i+1부터 시작해야 한다.
		 */  
		for(int i=0;i<n-1;i++) {
			for(int j=i+1;j<n;j++) {
				// i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스 
				if(visit[i]==true&&visit[j]==true) {
					team_start+=team[i][j];
					team_start+=team[j][i];
				}
				else if(visit[i]==false&&visit[j]==false) {
					// i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스 
					team_link+=team[i][j];
					team_link+=team[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int result=Math.abs(team_start-team_link);
		
		/*
		 * 두 팀의 점수차가 0이라면 가장 낮은 최솟값이기 때문에
		 * 더이상의 탐색 필요없이 0을 출력하고 종료하면 된다.
		 */
		if(result==0) {
			System.out.println(result);
			System.exit(0);
		}
		min=Math.min(result,min);
	}
}

 

[고찰]

 이번 문제에서 어려웠던 점은 팀을 나누는 것이었다. 1,2번이 같은 팀이 되는 것과 2,1번이 같은 팀이 되는 것은 같은 경우이기 때문에 중복을 방지하는 점도 함께 고려해야 했다.

 솔루션은 boolean 배열을 사용하여 팀에 따라 값을 달리 해주는 것이었다. 중복을 방지하기 위해서는 for문의 시작점을 증가시켜 주는 방식으로 해결할 수 있었고 점수를 계산하는 함수는 boolean 값에 따라 해당되는 팀끼리 점수를 더해주고 두 팀의 차를 절댓값으로 구해 최솟값을 갱신해주었다. 문제 자체는 어렵지 않았지만 재귀 함수에 익숙치 않음 때문인지 팀을 선정하는 방식이 어떻게 동작하는지 이해하는데 시간이 좀 걸렸다.