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

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

---

[접근 방법]

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

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

 

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

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

---

[JAVA 코드]

// 14889번 - 스타트와 링크
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];

        /*
        (1 ~ N) * (1 ~ N) 으로 입력받지 않고,
        (0 ~ N-1) * (0 ~ N-1)으로 입력 받은 이유는 
        차이가 없기 때문.
        */
        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){

        if (depth == N/2){
            /*
            방문여부에 따라 팀을 나눔.
            방문한 경우 : start 팀
            방문하지 않은 경우 : link 팀
            */
            calGap(); // 능력치 차이(gap)을 구하고, 최솟값(Min) 갱신

            return;
        }

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

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

        // 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. 어려웠던 점

- 방문 여부에 따라 팀을 나눈다는 것을 생각하지 못하였다.

(array를 사용하여 팀 멤버를 별도 저장 하지 않고, visit을 사용하여 곧바로 팀을 나눌 수 있음)

 

2. 알게된 점

- System.exit()를 사용하여 프로그램을 해당 위치에서 종료 시킬 수 있음.

(System.exit(1) : 비정상 종료(에러) / System.exit(0) : 정상 종료)

 

3. 개선 방향

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