[백준 / Java] 14889번 스타트와 링크

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 14889번 스타트와 링크

✔ 문제 설명

🚩 요구사항 분석

• 짝수로 인원이 주어지기에 start 팀이 정해지면 반대팀 link팀은 나머지 인원이 팀을 이루게된다.
  • boolean 배열로 스타트팀과 링크팀을 각각 나눈다.  
• 스타트팀과 링크팀의 빼서 값을 구한다.
• 재귀를 호출하면서 경우의 수를 확인해 나간다.
• 최소값이 0이 나온다면 값을 바로 출력해준다. 

 

🔑 문제풀이

dfs로 조합의개수를 추가하는 변수와 ,팀원 count 를 호출해 나갔다.

반절이 팀원이 되어야하기 때문에 count 가 N/2로 팀원이 다 짜지면

스타트팀과 링크팀의 value, 방문기록 visit을 확인해 최소값을 줄여나가는 방식으로 해당 문제를 풀었다.

 

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

public class Main {

    public static int N ;
    public static int count;
    public static int min = Integer.MAX_VALUE;
    public static int team_start ;
    public static int team_link;
    public static int [][] map ;
    public static boolean[] visit;



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        visit = new boolean[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            count = 0;
            while (st.hasMoreTokens()){
                map[count][i] = Integer.parseInt(st.nextToken());
                count++;
            }
        }

        dfs(0,0);
        System.out.println(min);
    }

    public static void dfs(int idx, int count){
        if (count == N /2){

            minimum();
            return;
        }

        for (int i = idx; i < N; i++) {
            if (!visit[i]){
                visit[i] = true;
                dfs(i+1,count+1);
                visit[i] = false;
            }

        }
    }

    public static void minimum(){
        team_start = 0 ;
        team_link = 0 ;
        
        for (int i = 0; i < N - 1; i++) {
            for (int j = i+1; j < N; j++) {
                if (visit[i] == true && visit[j] == true){
                    team_start += map[i][j];
                    team_start += map[j][i];
                }else if(visit[i] ==false && visit[j] == false){
                    team_link += map[i][j];
                    team_link += map[j][i];
                }
            }
        }
        int value = Math.abs(team_start - team_link);

        if(value == 0){
            System.out.println(value);
            System.exit(0);
        }

        min = Math.min(value,min);
    }

}