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

📖 문제

15661번: 링크와 스타트

 

 

 

💡  풀이 방식

• 백트래킹

부분집합 (재귀) 을 활용해 팀을 나누고, 각 팀별로 능력치를 합하고 그 차이를 최솟값과 비교해 정답으로 출력한다.

 

 

💥 유의사항

두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. → 부분집합

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] S;
    static boolean[] chk; // 🔔 해당 사람 뽑았는지 확인용 배열
    
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        S = new int[N][N];
        chk = new boolean[N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0);
        System.out.println(min);
    }
    
    private static void dfs(int cnt) { // 🔔 cnt : 사람
        if(cnt == N) {  // [종료 조건] 마지막 원소까지 부분집합에 다 고려되었을 때
            int start = 0;
            int link = 0;
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = i + 1 ; j < N ; j++) {
                    if(chk[i] != chk[j])   continue;
                    
                    if(chk[i])  start += S[i][j] + S[j][i];
                    else        link  += S[i][j] + S[j][i];
                }
            }
            
            min = Math.min(min, Math.abs(start - link));
            return;
        }
 
        // 해당 cnt번 사람 선택해 스타트 팀에 넣음
        chk[cnt] = true;
        dfs(cnt + 1);
        
        // 해당 cnt번 사람 비선택해 링크 팀에 넣음
        chk[cnt] = false;
        dfs(cnt + 1);
    }
}
 

 

 

➕ 다른 풀이 방식

(조합 ver.) 팀의 인원 수를 (1, N-1) (2, N-2), .. (M, N-M) 이렇게 모든 경우에 대해 탐색하며 진행하셨다. 

그리고 dfs 방식할 때 재귀함수에서 (인자, 뽑은 갯수) 인자로 들고 다니면서 내가 작성하던 방식과 같게 하심

[백준] 15661 링크와 스타트 - 완전탐색 (DFS) JAVA

[ BOJ ][JAVA][15661] 링크와 스타트

---

💦 어려웠던 점

- 부분집합을 써야겠단 생각까지는 들었는데 백트래킹 함수를 제대로 작성했는지에 확신이 없었다. (그리고 실제로 틀리게 작성했었다) 다시 복습을 해야겠따..

- 백트래킹 깊이를 어떻게 바꾸지?에 대한 부분이 어려웠다.

- 스타트와 링크 문제와 비슷하다 하여 이 문제와 다른 부분집합 문제들을 풀어보도록 하겠다.

 

🧐 새로 알게 된 내용

부분집합 개념!!!

[Java]부분 집합(Subset)과 멱집합(Power Set)

부분집합 PowerSet (Java)

[Java] 부분집합(Subset)

[알고리즘] 부분집합(Subset)

 

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

---

(참고)

✔ 풀이 참고 : https://sa11k.tistory.com/56 , https://bbangson.tistory.com/50

✔ 내가 진행하려고 했던 방향과 같으심

[백준] 15661번 링크와 스타트 풀어보기 [Java]

 

 

이거 완전 재귀의 총집합!!!

[Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)