[백준, 14889번] 스타트와 링크 (백트래킹, 브루트 포스, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 스타트와 링크" 문제는 짝수를 보장하는 N이 주어지고, 팀을 나누는 문제입니다. 팀원들을 두 개의 팀으로 나누어 각 팀의 능력치 차이를 최소화하는 것을 목표로 합니다.

 

문제에서의 핵심은 "팀을 나누는 방법"입니다. 이때, 두 팀이 겹치거나 비는 경우는 배제해야 합니다. 따라서 문제를 풀 때 아래의 사항을 고려하면 됩니다:

1. 00이나 11과 같은 경우는 고려할 필요가 없습니다.
   • 이 의미는 한 팀이 비어 있거나 모든 사람이 한 팀에 속하는 경우입니다.
   • 문제에서 "N명을 정확히 반으로 나누는 상황(N은 짝수)"이기 때문에, 한 팀이 비거나 모든 사람이 한 팀에 속하는 경우는 애초에 유효하지 않습니다.
2. 조합을 통해 팀을 나누되, 정확히 반씩 나눠야 합니다.
   • 예를 들어, N = 4라면 {1, 2}와 {3, 4} 또는 {1, 3}과 {2, 4}처럼 팀을 나누어야 합니다.

---

능력치 Sij는 i번 사람과 j번 사람을 의미하는데, 문제를 자세히 보면 i와 j의 합을 구해야합니다. 따라서 i + j 나 j + i 는 같은 수식입니다. 즉, 조합을 통해 팀원을 선택하고, 선택된 팀원들 간의 능력치 합을 계산하면 됩니다.

 

정리하자면 팀을 정확히 N /2 로 중복없이 나누고, 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력하는 문제입니다.

 

전체 코드

 

1. static 변수

    static int N ;
    static boolean[] visited;
    static int[][] map;
    static int minDiffValue;

• N = 전체 인원 수를 저장하는 변수
• visited = 각 인원이 어느 팀에 속하는지 표시하는 배열
  • true: 스타트 팀
  • false: 링크 팀
• map = 두 명이 한 팀이 되었을 때의 능력치를 저장하는 2차원 배열
  • map[i][j] = i번 사람과 j번 사람이 같은 팀일 때 더해지는 능력치
• minDiffValue = 두 팀의 능력치 차이 중 가장 작은 값을 저장
  • Integer.MAX_VALUE로 초기화하여 첫 비교에서 현재 차이값이 저장될 수 있도록 함

 

2. main 문 

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N];
        minDiffValue = Integer.MAX_VALUE; // 가장 큰 값으로 초기화 (0 방지)

        for (int i = 0; i < N; i++) {
            token = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(token.nextToken());
            }
        }

        // 팀 나누기
        divideTeams(0,0);
        System.out.println(minDiffValue);
    }

 

먼저 main문에서 입력을 BufferedReader 클래스를 사용하여 입력을 받아주고, StringTokenizer 클래스를 사용하여 입력을 공백을 기준으로 토큰으로 분리해줍니다.

 

그리고 static 변수를 초기화 해줍니다. 이 때 minDiffValue는 능력치 차이가 최솟값이 되는 값이 저장되는 변수로, MAX_VALUE를 사용하여 아주 큰 값으로 초기화 해줍니다. MAX_VALUE로 초기화하지 않는다면 int형의 기본값인 0으로 인해 계속해서 0이 저장되기 때문입니다.

 

3. divideTeams : 팀을 나누기 위한 함수

 private static void divideTeams(int order, int count) {
        if(count == N / 2){
            diffScore();
            return;
        }

        for (int i = order; i < N ; i++) {
            if (!visited[i]) { // 방문하지 않았다면
                visited[i] = true; // 방문 처리
                divideTeams(i + 1, count + 1);
                visited[i] = false;
            }
        }
    }

 

divideTeams 함수는 정확히 N / 2명 씩 팀을 나누기 위한 함수입니다.

 

백트래킹(backtracking) 알고리즘을 사용하여, 모든 가능한 팀 조합을 탐색합니다.

1. 탈출(기저) 조건
   • count가 N/2가 되면 한 팀에 정확히 절반의 인원이 배정된 것
   • 이때 diffScore() 함수를 호출하여 두 팀의 능력치 차이를 계산
2. 재귀 호출
   • order부터 N까지 순회하면서 팀원을 선택
   • 방문하지 않은 인원(i)을 발견하면:
     • visited[i]를 true로 설정(스타트 팀에 배정)
     • 다음 인원을 선택하기 위해 재귀 호출
     • 재귀 호출이 끝나면 visited[i]를 false로 복구(백트래킹)

---

여기서 중요한 점은 조합을 구현하기 위해 i + 1을 사용한다는 것입니다. 순서가 아닌 선택 여부가 중요하기 때문에

• {1, 2}와 {2, 1}은 같은 팀으로 취급
• divideTeams(i + 1, count + 1)을 통해 이전에 선택한 숫자는 다시 선택하지 않음
• 이를 통해 중복 없는 조합을 구현

이러한 방식으로 가능한 모든 팀 조합을 확인하며, 각 조합에서의 능력치 차이를 계산하여 최솟값을 찾습니다.

[Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기

 

4. diffScore : 점수 차이를 구하는 함수

private static void diffScore() {
        // Start 팀과 Link 팀의 점수를 저장할 변수 초기화
        int teamStart = 0; int teamLink = 0;

        for (int i = 0; i < N ; i++) {
            for (int j = i + 1; j < N; j++) {
                if(visited[i] && visited[j]){ // team start
                    teamStart += map[i][j] + map[j][i];
                }else if(!visited[i] && !visited[j]){
                    teamLink += map[i][j] + map[j][i];
                }
            }
        }

        int diff = Math.abs(teamStart - teamLink);
        minDiffValue = Math.min(diff,minDiffValue);
    }

 

diffScore 함수는 스타트팀과 링크팀의 점수의 합을 구하고, 최솟값을 업데이트하는 함수입니다.

1. 능력치 계산
   • visited가 true인 경우 스타트 팀의 능력치
   • visited가 false인 경우 링크 팀의 능력치
   • 각 팀의 능력치는 i번 사람과 j번 사람이 같은 팀일 때의 Sij + Sji의 합
2. 차이값 계산 및 최솟값 갱신
   • 두 팀의 능력치 차이의 절댓값을 구함
   • 차이를 구하는 것이기 때문에 음수든 양수든 절댓값으로 계산
   • 이전까지의 최솟값과 비교하여 더 작은 값으로 갱신