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

🔺 문제

14889번: 스타트와 링크

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] map;
    static boolean[] visited;
    
    static int min = Integer.MAX_VALUE;
    
    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];
        visited = new boolean[N];
        
        for(int i = 0 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        combi(0, 0);
        System.out.println(min);
    }
    
    private static void combi(int idx, int depth) {
        if(depth == N / 2) {
            diff();
            return;
        }
        
        for(int i = idx ; i < N ; i++) { // 팀 나누기
            if(!visited[i]) {
                visited[i] = true;
                combi(i + 1, depth + 1); // 재귀 호출
                visited[i] = false;      // 다른 조합 구성할 수 있게 원상복구          
            }
        }
    }
    
    /*** 두 팀 (방문한 팀 vs 방문 안 한 팀) 능력치 차이 계산 메소드 ***/
    private static void diff() {
        int teamS = 0;
        int teamL = 0;
        
        for(int i = 0 ; i < N - 1 ; i++) {
            for(int j = i + 1 ; j < N ; j++) {
                
                // 스타트 팀 (= 방문한 팀) 점수 더하기 
                if(visited[i] && visited[j]) {
                    teamS += map[i][j];
                    teamS += map[j][i];
                }
                // 링크 팀 (= 방문 안 한 팀) 점수 더하기
                else if(!visited[i] && !visited[j]) {
                    teamL += map[i][j];
                    teamL += map[j][i];
                }
            }
        }
        
        // 두 팀 점수 차이
        int diff = Math.abs(teamS - teamL); 
        if(diff == 0) {
            System.out.println(0);
            System.exit(0);    // 프로그램 종료
        }
        
        min = Math.min(min, diff);
    }
}

✅ 해결 아이디어
✔ 백트래킹
- 숫자를 N / 2개 뽑으면 두 팀 간 점수 차이 구하기
- 뽑은 숫자들에 대해 "순열"로 각 팀 능력치 계산 (diff 메소드)
   └ 스타트 팀 : visited[i] == true && visited[j] == true 인 팀
   └ 링크 팀     : visited[i] == false && visited[j] == false인 팀

 

 

💥 유의사항

• 70번째 줄에 System.exit(0)해야 0 출력하고 프로그램이 제대로 종료됨. 안 그러면 재귀 뒤쪽까지 돌아서 틀림

•  방문 배열을 잊지 말고 잘 사용하자..

 

 

---

🔺 다른 풀이들

 

[백준] 14889번 스타트와 링크 - Java, 자바

---

💬 느낀 점

백트래킹 감은 잡았는데 아직까지는 놓치는 부분이 있어서 풀이 참고를 해야하는 것 같다....

후하 정복해주겠다....,,,ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 항상 감사드리는 선생님들..🥺🥺

[백준] 14889번 : 스타트와 링크 - JAVA [자바]

 

[백준][JAVA알고리즘]14889번 풀이(스타트와 링크) - 초보도 이해하는 풀이

 

[백준] 14889번 - "스타트와 링크" (Java)