[백준] 15661번 - 링크와 스타트 (JAVA)

[백준] 15661번 - 링크와 스타트 (JAVA)

---

[접근 방법]

DFS를 사용하여 해결한 문제였다.

가장 핵심적인 부분은 "방문 여부에 따라서 팀을 나눈다." 이다.

 

visit 배열을 사용하여 0~N-1까지 수 중에서 방문 한 값은 Team : Start에 포함되고,

방문하지 않은 값은 Team : Link에 포함된다.

 

여기까지는 14889번 - <스타트와 링크> 문제와 동일하다.

다른 점은 "두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다." 

즉, 두팀의 인원수가 서로 다를 수 있다는 것이다.

 

기존 문제는 dfs에서 depth == N/2인 경우 calGap()을 실행 시켜 두 팀간의 능력치 차이를 탐색하였지만,

이 문제는 "팀원 수와 관계없이 능력치 차이를 조사" 한다.

 

14889번 - <스타트와 링크>

https://notorious.tistory.com/224

---

[JAVA 코드]

// 15661번 - 링크와 스타트
import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[][] stats; // 능력치
    static boolean[] visit;

    static int Min = Integer.MAX_VALUE; // 최솟값

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j=0; j<N; j++){
                stats[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1. dfs 실행
        dfs(0, 0);

        // 2. 최솟값 출력
        System.out.println(Min + "\n");     
    }

    public static void dfs(int at, int depth){

        for(int i=at; i<N; i++){

            if(!visit[i]){
                visit[i] = true;
                dfs(i + 1, depth + 1);
                visit[i] = false;
            }

            // 팀원 수와 관계없이 능력치 차이를 조사
            calGap();
        }

        // return;
    }

    public static void calGap(){
        int team_start = 0;
        int team_link = 0;

        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N; j++){

                // i와 j에 모두 방문한 경우 : i와 j 모두 Team Start에 포함
                if (visit[i] == true && visit[j] == true){
                    team_start += stats[i][j];
                    team_start += stats[j][i];
                }

                // i와 j에 모두 방문하지 않은 경우 : i와 j 모두 Team Link에 포함
                else if (visit[i] == false && visit[j] == false){
                    team_link += stats[i][j];
                    team_link += stats[j][i];
                }
            }
        }

        // 두팀의 능력치 차이 (절댓값을 사용 : 양수)
        int gap = Math.abs(team_start - team_link);

        // gap이 0인 경우 최솟값이 더 이상 갱신될 수 없는 최솟값 이므로,
        // 곧바로 출력하고 프로그램 종료
        if (gap == 0){
            System.out.println(gap);
            System.exit(0); // 프로그램 종료 (0 : 정상 종료, 1: 오류 종료)
        }

        // 최솟값 갱신
        Min = Math.min(Min, gap);
    }

}

---

[Rewind]

1. 어려웠던 점

-

 

2. 알게된 점

-

 

3. 개선 방향

- 응용 문제를 반복하여 풀어서 숙달해야 함.