![[백준,BOJ 14889] 스타트와 링크(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbFLvhM%2FbtqzZ2iVur5%2FxU1Yjn2KozJFv8LcFHN120%2Fimg.png)
-내 생각
단계별 풀어보기 백트래킹 분류에 있는 마지막 문제로 이 문제 역시 삼성 기출문제라고 한다. 문제 자체의 이해는 어렵지 않지만, 주의해야 할 부분이 하나 있는데, 예제 입력 2번의 경우 사람의 수는 6명이므로 3:3으로 나누어 게임을 진행한다. 이때 예를 들어 3명으로 이루어진 팀 중 한 팀의 구성원을 1번, 2번 3번을 선택했을 때 팀의 능력치는 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)의 합이 된다는 점이다. 처음에 풀 때는 예제 입력 1을 기준으로 생각하여서 고려하지 못했던 부분이다.
또한 이 문제를 풀기 위해서 어떻게 풀어야 할지 고민하는 과정에서 DFS를 어떤 방식으로 수행해야 할 지 고민이었는데, 처음 시도한 방법은 2중 반복문으로 한 명의 사람을 고정 후 다음 사람을 선택하는 식으로 진행하려 했는데, 재귀 호출의 종료가 애매해져 실패했다.
-해법
결국 생각해낸 방식은 n/2의 사람 수만큼 방문 배열을 체크해주고 (예를 들어, 예제 입력 1의 경우 4명이므로 2명의 사람의 방문 배열을 표시 후) n/2의 사람 수 만큼 체크했을 때 체크된 사람들과 체크되지 않은 사람들의 능력치 합을 구하고자 했다. 그러나 이 방법의 경우에는 모든 경우의 수마다 방문 배열을 탐색해야 해서 시간 초과가 발생했다. 결국 다른 분들의 블로그를 참고해서 계산을 하는 과정에서 방문 배열을 사용하는 것이 아니라 체크된 원소들을 별도의 배열에 저장 해 두면, 모든 방문 배열을 탐색할 필요가 없이 저장해 둔 배열만 탐색하면 되기 때문에 시간 단축이 가능했다.
또한 이 문제에서는 계산 과정과 재귀 호출의 반복문 부분에서 주의해야 할 부분이 있는데, 그것은 바로 조합의 개념이다. 능력치를 계산하는 과정에서는 예를 들어 (1,2) 사람들의 능력치를 계산할 때 동시에 (2,1)의 능력치 역시 계산이 가능하기 때문에 이 부분에서 시간 단축이 가능하고, 또한 재귀호출의 반복문에서 1번 사람을 시작으로 1번, 2번, 3번의 사람이 선택된 후 다음 시작이 2번 사람일 때 2번, 1번, 3번을 선택하게 되면 앞선 계산과정과 동일하므로 배제해 주어야 할 필요가 있다.
자세한 내용은 코드를 보면서 이해해보자.
import java.util.*;
public class Main {
static int n; // 사람 수 입력 변수
static int map[][],check[]; // 능력치 판 2차원 배열, 각 사람 수의 방문 배열
static int min = Integer.MAX_VALUE; // 최솟값을 찾기 위한 변수
//DFS메소드, 조합의 개념을 사용하므로 별도의 시작 부분을 전달해 주어야 한다.
static void dfs(int start,int cnt) {
if(cnt == n/2) { // DFS 종료 부, n/2의 사람 수만큼 선택하면 계산을 시작한다.
cal(); // 최솟값을 계산하는 메소드
return;
}
// 전달받은 start+1 부터 반복해야 중복을 배제할 수 있다.
// 예를 들어, 1번 2번 3번 사람을 선택했을 때 계산을 완료 후
// 2번 사람이 첫 번째 일 때 3번 사람부터 탐색하는 것이다.
// 자연스레 1번 사람은 배제가 된다.
for(int i=start+1;i<n;i++) {
if(check[i]==0) { // 방문하지 않은 사람이면
check[i]=1; // 방문 처리 후
dfs(i,cnt+1); // 재귀 호출, 시작 값과 선택된 사람의 수를 넘겨준다.
check[i]=0; // 백 트래킹
}
}
}
static void cal() { // n/2 수의 사람을 선택 후 계산하는 메소드
int start =0,link =0; // start팀과 link팀의 능력치가 저장되는 변수
int a[] = new int[n/2]; // 선택된 사람들과 선택되지 않은 사람들이 저장 될 배열들
int b[] = new int[n/2];
int a_index=0,b_index=0; // 위의 두 배열에 값을 저장하기 위한 인덱스 변수
for(int i=0;i<n;i++) { // 방문 배열을 탐색한다.
if(check[i]==1) { // 선택된 사람들의 경우
a[a_index++] = i; // a 배열에 저장
}else { // 나머지 사람들은
b[b_index++] = i; // b 배열에 저장
}
}
// a와 b배열에 저장 된 사람들의 능력치를 계산
start = divide(a);
link = divide(b);
// 두 팀의 능력치 차이를 절댓값화 하여
int result = Math.abs(start-link);
// 최솟값을 찾는다.
min = Math.min(result,min);
}
static int divide(int[] arr) { // 두 팀의 능력치를 계산하는 메소드
int result = 0;
for(int i=0;i<arr.length;i++) { // 두 사람을 선택해 능력치를 계산
for(int j=i+1;j<arr.length;j++) { // 조합이므로 앞선 사람의 다음 사람부터 탐색
result = result + map[arr[i]][arr[j]] +map[arr[j]][arr[i]] ; // 두 경우를 모두 더해준다.'
}
}
return result; // 능력치 결과 리턴
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new int[n][n];
check = new int[n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map[i][j] = sc.nextInt();
}
}
dfs(-1,0); // 0번 인덱스부터 시작하므로 -1을 전달.
System.out.println(min);
}
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
class Main {
static BufferedReader br;
static BufferedWriter bw;
static int min = Integer.MAX_VALUE;
static void cal(int[][] s,boolean[] check) {
int start = 0;
int link = 0;
for(int i=0;i<s.length-1;i++) {
for(int j=i+1;j<s[i].length;j++) {
if( check[i] == true && check[j] == true) {
start += s[i][j];
start += s[j][i];
}else if( check[i] == false && check[j] == false) {
link += s[i][j];
link += s[j][i];
}
}
}
min = Math.min(Math.abs(start-link), min);
}
// DFS 메소드
static void dfs(int[][] s,boolean[] check,int idx,int cnt) {
if(cnt == s.length/2) {
cal(s,check);
return;
}
for(int i=idx;i<s.length;i++) {
if(!check[i]) {
check[i] = true;
dfs(s,check,i+1,cnt+1);
check[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int s[][]=new int[n][n];
boolean check[] = new boolean[n];
for(int i=0;i<s.length;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<s[i].length;j++) {
s[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(s,check,0,0);
bw.write(String.valueOf(min));
bw.flush();
bw.close();
br.close();
}
}