[백준] code.plus(브루트포스-재귀,JAVA)15661번, 링크와 스타트

문제 링크

15661번: 링크와 스타트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제를 풀어보기 전 조건이 살짝 다르지만 더 간단한 문제가 있으니 그 문제에 대한 링크를 참고해주세요.

[백준] 단계별로 풀어보기(단계:14,백트래킹,JAVA)14889번, 스타트와 링크

 

이 문제에 핵심은

1. 링크와 스타트팀의 능력치 차이가 최소이어야 한다.

2. 링크와 스타트팀의 인원은 최소 한 명 이상이어야 한다.

 

배열

ability  : i와 j가 팀을 이루었을 때 능력치를 저장하는 2차원 배열

 

check : 인덱스 인원이 링크팀에 있는지 확인하는 배열

 

 

위에 ability, check와 재귀를 통해 능력치 최소의 차를 구하였습니다.

 

재귀를 통해 모든 경우의 수에 대한 능력치 차를 비교하여 최소값을 결과로 출력하였습니다.

 

능력치의 합은 만약 1, 2, 3명이 링크팀이면

ability[1][2] + ability[2][1] = 1, 2가 팀이 되었을 때 능력치 합

ability[1][3] + ability[3][1] = 1, 3이 팀이 되었을 때 능력치 합

ability[2][3] + ability[3][2] = 2, 3이 팀이 되었을 때 능력치 합

결과적으로

(ability[1][2] + ability[2][1]) + (ability[1][3] + ability[3][1]) + (ability[2][3] + ability[3][2])

= 1, 2, 3이 링크팀일 때 능력치의 합

 

문제에 해결알고리즘은

1. 배열 ability를 입력값으로 초기화한다.

2. 재귀를 통해 모든 경우의 수를 구한다.

3. 모든 경우의 수에 능력치 차를 비교하여 최소값을 구하고 결과로 출력한다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 ability 배열을 초기화하였습니다.
• 모든 경우 중에 능력치 최소차를 구하는linkAndStart 함수를 만들었습니다.
• BufferedWriter에 모든 경우의 수에서 능력치의 차 최소값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bestCost는 재귀를 사용하여 팀의 모든 경우의 수를 구해서 능력치의 차 최소값을 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] ability;		//i,j의 팀이 되었을 때 능력치의 합 저장 배열
	public static boolean[] check;		//인덱스의 인원 링크팀인지 확인 배열
	public static int N,minValue = Integer.MAX_VALUE;	//인원, 결과
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화-----------
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	ability = new int[N][N];
    	check = new boolean[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<N;j++) {
    			ability[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
        linkAndStart(0);		//함수 실행
    	bw.write(minValue + "\n");		//최소값 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //--------능력치 차 최소값 구하는 함수--------
    public static void linkAndStart(int depth) {
    	if(depth==N) {		//팀 나누기 완료시
    		int tempLink = 0;	//링크팀 능력치 합
    		int tempStart = 0;	//스타트팀 능력치 합
    		for(int i=0;i<N;i++) {
    			for(int j=i+1;j<N;j++) {
    				if(check[i]!=check[j])	//i와j가 서로 다른 팀일 때
    					continue;
    				if(check[i])		//i와 j가 링크팀일 때
    					tempLink += ability[i][j] + ability[j][i];
    				else		//i와 j가 스타트팀일 때
    					tempStart += ability[i][j] + ability[j][i];
    			}
    		}
            //능력치 최소값 비교
    		minValue = Math.min(minValue, Math.abs(tempLink - tempStart));
    		return;
    	}
    	check[depth] = true;
    	linkAndStart(depth+1);	//해당 인원 링크팀일 때
    	check[depth] = false;
    	linkAndStart(depth+1);	//해당 인원 스타트팀일 때
    			
    	}
    }