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

문제 링크

14889번: 스타트와 링크

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

백트래킹이란 깊이 우선 탐색을 바탕으로 탐색 중 오답을 만나면 이전 분기점으로 돌아가서 다른 해결방법이 있는지 확인하고 더 이상 없으면 더 이전에 분기점으로 돌아가서 해결방법을 찾아보는 방식입니다.깊이 우선 탐색은 모든 경우의 수를 검색하게 되지만 백트래킹은 오답으로 판단될시 그에 해당하는 자식 노드들은 모두 무시하고 넘어가기 때문에 더욱 효율적으로 코드가 진행됩니다.

검은색 : 실행되지 않은 노드

빨간색 : 오답으로 판단한 노드

초록색 : 올바른 값이라고 판단한 노드

위에 그림처럼 부모노드가 틀리다고 판정되면 자식노드 무시하고 이전 분기점으로 돌아가서 확인하는 방식으로 코드가 전개되어 가는 방식입니다.

 

이 문제를 해결할 때에 백트래킹을 통해 팀의 경우의 수를 구하여 능력치에 차를 구하였습니다.

문제에서 0은 최소값이라고 설명하였기 때문에 만약 차이가 0이 나온다면 시스템을 종료시켰습니다.

팀은 반반으로 나눠지기 때문에 백트래킹 깊이를 전체 인원수의/2해주었습니다.

 

• 능력치 숫자를 저장할 배열 ablity을 만들었습니다.
• 팀 경우의 수를 확인하는 배열 check을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 능력치 차 최소값 구하는 함수 startAndlink을 만들었습니다.
• 능력치에 차를 구하는 함수 ablityCal를 만들었습니다.
• System.out.println()을 사용하여 결과를 출력하였습니다.

• 0이 최소값이기 때문에 차이값을 절대값으로 표현하기 위해 Math.abs를 사용하여 구하였습니다.
• 차이가 0일 때 시스템을 종료하기 위해 System.exit(0)을 사용하였습니다.
• 차이값 비교를 위하여 Math.min을 사용하였습니다.
• 위에 알고리즘을 토대로 startAndlink를 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] ablity;		//능력치 저장 배열
	static int size,result=Integer.MAX_VALUE;	//크기, 결과
	static boolean[] check;		//확인 배열
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //----------------입력값 저장 및 배열 초기화
    	size = Integer.parseInt(br.readLine());
    	ablity = new int[size][size];
    	check = new boolean[size];
    	StringTokenizer st;
    	for(int i=0;i<size;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<size;j++)
    			ablity[i][j] = Integer.parseInt(st.nextToken());
    	}
    	startAndlink(0,0);	//함수 실행
    	System.out.println(result);		//결과 출력
    	br.close();
	}
    //-----------------백 트래킹 함수----------
	public static void startAndlink(int depth, int current) {
		if(depth==size/2) {	//인원 정해질 시 능력치 계산
			ablityCal();
			return;
		}
        //백트래킹 실행
		for(int i=current;i<size;i++) {
			if(!check[i]) {
				check[i] = true;
				startAndlink(depth+1,i+1);
				check[i]=false;
			}
		}
		return;
	}
    //---------------능력치 계산 함수-------------
	public static void ablityCal() {
		int startScore=0, linkScore=0;
		for(int i=0;i<size-1;i++) {
			for(int j=i+1;j<size;j++) {
				if(check[i] && check[j])	//start팀
					startScore += ablity[i][j] + ablity[j][i];
				else if(!check[i] && !check[j])		//link팀
					linkScore += ablity[i][j] + ablity[j][i];
			}
		}
		int dif = Math.abs(startScore-linkScore);
		if(dif==0) {		//0은 최소값
			System.out.println(dif);
			System.exit(0);		//시스템 종료
		}
		result = Math.min(result, dif);
	}
}