[백준] 백트래킹 (14889 : 스타트와 링크)

문제

---

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

해설

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    //스타트팀, 링크팀 둘 중 하나에만 속할 수 있기 때문에 팀 소속 여부를 판단하기 위한 배열
    static boolean visit[];
    //최솟값을 저장하기 위한 배열
    static int min = 1000000000;
    //입력받은 N * N 능력치 배열
    static int status[][];
    
    //스타트팀, 링크팀에 속한 인원을 저장하기 위한 배열
    static int start[];
    static int link[];
    
    //스타트팀, 링크팀에 속한 인원들의 조합을 구하기 위한 임시 배열
    //스타트 : (1,2,3), 링크 : (4,5,6)일 때 각각 nC2를 통해 능력치 합을 구하기 위해 사용
    //즉, 팀 내의 두 선수의 시너지를 구하기 위한 배열
    static int temp[];
    
    //스타트, 링크팀의 능력치 합
    static int start_Status = 0;
    static int link_Status = 0;


    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        //필요한 변수들 초기화
        status = new int[N][N];
        //스타트팀과 링크팀을 N/2명으로 구성됨
        start = new int[N / 2];
        link = new int[N / 2];
        //총 선수는 N명
        visit = new boolean[N];
        //두 선수의 시너지를 구하기 위한 배열
        temp = new int[2];
		
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                status[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs14889(N, 0, 0);
        sb.append(min);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    //스타트, 링크 팀의 인원을 배정하기 위한 재귀함수
    private static void dfs14889(int N, int depth, int pre) {
        //스타트팀의 인원이 N/2명이라면 재귀함수 탈출 및 팀의 시너지 점수 계산
        if (N / 2 == depth) {
            int idx = 0;
            //스타트팀이 아닌 인원은 모두 링크팀이다.
            for (int i = 0; i < visit.length; i++) {
                if (!visit[i]) {
                    link[idx] = i;
                    idx++;
                }
            }
            //스타트팀의 시너지 점수 합 (마지막 매개변수 sel = 0)
            calc_status(N / 2, 2, 0, 0,0);
            //링크팀의 시너지 점수 합 (마지막 매개변수 sel = 1)
            calc_status(N / 2, 2, 0, 0, 1);
            
            //두 시너지 점수의 차이의 절대값과 지금까지 모든 케이스의 최솟값을 비교 후 갱신
            min = (int) Math.min(Math.abs(start_Status - link_Status), min);
            //두 변수 초기화
            start_Status = link_Status = 0;
            return;
        }
        //조건에 맞게 스타트팀을 구성
        for (int i = pre; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                start[depth] = i;
                dfs14889(N, depth + 1, start[depth]);
                visit[i] = false;
            }
        }
    }
    //스타트팀 or 링크팀에 소속된 인원들의 시너지 합을 구하는 재귀함수
    private static void calc_status(int N, int M, int depth, int pre, int sel) {
        //2명을 선택했으면 계산
        if (M == depth) {
            int n = temp[0]; //첫번째 선택된 인원
            int m = temp[1]; //두번째 선택된 인원
            //sel == 0 이면 스타트팀, 1이면 링크팀
            //1과 2의 시너지는 2와 1의 시너지와 다를 수 있으므로 두 경우를 모두 더한다/
            if (sel == 0)
                start_Status += (status[n][m] + status[m][n]);
            else
                link_Status += (status[n][m] + status[m][n]);
            return;
        }
        //해당 팀에 소속된 인원들을 중복이 없는 조합으로 모든 경우를 탐색(nC2)
        for (int i = pre; i < N; i++) {
            temp[depth] = sel == 0 ? start[i] : link[i];
            calc_status(N, M, depth + 1, i+1, sel);
        }
    }
}

코드가 생각보다 길게 작성되어 나눠서 알아보자

---

main()

---

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        //필요한 변수들 초기화
        status = new int[N][N];
        //스타트팀과 링크팀을 N/2명으로 구성됨
        start = new int[N / 2];
        link = new int[N / 2];
        //총 선수는 N명
        visit = new boolean[N];
        //두 선수의 시너지를 구하기 위한 배열
        temp = new int[2];
		
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                status[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs14889(N, 0, 0);
        sb.append(min);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

 

먼제 main() 메서드를 보면 필요한 변수들을 초기화해주고, 팀을 구성하기 위한 재귀함수 dfs14889()를 호출한다.

---

dfs14889() : 스타트, 링크팀에 인원 분배

---

    //스타트, 링크 팀의 인원을 배정하기 위한 재귀함수
    private static void dfs14889(int N, int depth, int pre) {
        //스타트팀의 인원이 N/2명이라면 재귀함수 탈출 및 팀의 시너지 점수 계산
        if (N / 2 == depth) {
            int idx = 0;
            //스타트팀이 아닌 인원은 모두 링크팀이다.
            for (int i = 0; i < visit.length; i++) {
                if (!visit[i]) {
                    link[idx] = i;
                    idx++;
                }
            }
            //스타트팀의 시너지 점수 합 (마지막 매개변수 sel = 0)
            calc_status(N / 2, 2, 0, 0,0);
            //링크팀의 시너지 점수 합 (마지막 매개변수 sel = 1)
            calc_status(N / 2, 2, 0, 0, 1);
            
            //두 시너지 점수의 차이의 절대값과 지금까지 모든 케이스의 최솟값을 비교 후 갱신
            min = (int) Math.min(Math.abs(start_Status - link_Status), min);
            //두 변수 초기화
            start_Status = link_Status = 0;
            return;
        }
        //조건에 맞게 스타트팀을 구성
        for (int i = pre; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                start[depth] = i;
                dfs14889(N, depth + 1, start[depth]);
                visit[i] = false;
            }
        }
    }

해당 메서드는 스타트팀의 인원을 분배하고 남은 인원을 링크팀에 배정하였다.

여기서 생각해보아야할 조건을 알아보면 아래와 같다.

• 스타트팀은 N/2명으로 구성되어있다 (링크팀도 동일)
• 한명의 선수는 한팀에만 소속가능하며, 동일한 선수가 같은 팀에 소속될 수 없다.
  (즉 start : (1,1,1)의 경우를 배제해야한다.)

그렇다면 이는 15649 : N과 M (1)번과 동일하다고 볼 수 있다.

15649 : N과 M (1) 해설 : https://beudicri.tistory.com/93

[백준] 백트래킹 (15649 : N과 M (1))

---

동작방식은

1. 스타트팀을 위의 조건에 맞게 구성한다.
2. 스타트팀의 인원이 N/2명이 된다면, 선택되지 않은 인원은 모두 링크팀에 배정된다.
   (idx와 visit을 통해 링크팀 인원을 배열에 저장한다.)
3. calc_status() 메서드의 마지막 인자로,  0과 1을 통해 스타트팀, 링크팀의 시너지 합을 구한다.

---

calc_status() 메서드 : 스타트팀, 링크팀의 시너지 합을 계산하는 메서드

---

    //스타트팀 or 링크팀에 소속된 인원들의 시너지 합을 구하는 재귀함수
    private static void calc_status(int N, int M, int depth, int pre, int sel) {
        //2명을 선택했으면 계산
        if (M == depth) {
            int n = temp[0]; //첫번째 선택된 인원
            int m = temp[1]; //두번째 선택된 인원
            //sel == 0 이면 스타트팀, 1이면 링크팀
            //1과 2의 시너지는 2와 1의 시너지와 다를 수 있으므로 두 경우를 모두 더한다/
            if (sel == 0)
                start_Status += (status[n][m] + status[m][n]);
            else
                link_Status += (status[n][m] + status[m][n]);
            return;
        }
        //해당 팀에 소속된 인원들을 중복이 없는 조합으로 모든 경우를 탐색(nC2)
        for (int i = pre; i < N; i++) {
            temp[depth] = sel == 0 ? start[i] : link[i];
            //이전보다 큰 인덱스를 매개변수로 넘겨준다.
            calc_status(N, M, depth + 1, i+1, sel);
        }
    }

해당 메서드는 각 팀의 모든 시너지의 합을 구해주는 메서드이다.

모든 시너지를 구하기 위해서는 N명의 팀원 중 2명을 뽑아서 시너지를 합해줘야한다.

(즉, start : (1,2,3) => (1,2), (1,3), (2, 3)의 3개의 조합이 가능하며,
(1,2 != 2,1)인 경우가 있을 수 있기 때문에 이를 각각 더해주어야 한다.)

 

여기서 알아두어야할 것이 있다.

위의 dfs14889() 메서드를 통해 팀을 구성하면, 기본적으로 오름차순으로 인원이 배정되어 있다.

또한, 중복이 없는 조합으로 탐색해야하기 때문에 앞의 나온 값보다 뒤의 값이 커야한다.

 

그렇다면 이는 15650 : N과 M (2)번과 동일하다고 볼 수 있다.

15650 : N과 M (2) 풀이 : https://beudicri.tistory.com/94

[백준] 백트래킹 (15650 : N과 M (2))

하지만, 이 문제 풀이와 다르게, 해당 배열에 저장된 값을 인자로 넘겨주면 안되고 인덱스를 넘겨주어야 한다.

왜냐하면) start : (1,3,6)일 때, 이전 값인 1을 넘겨주면 for문에서 2부터 탐색하는데,
2는 해당 팀에 소속되지 않은 인원이기 때문에 인덱스를 넘겨주어 start팀의 인덱스 0 (= 1)보다 큰 인덱스부터 시작하면
1, 2 (= 3, 6) 중에서 선택할 것이다.

---

동작방식은

1. 해당 팀에 속한 인원들의 조합을 구한다.
2. 2명을 구성하게 되면, 두 명 각각의 시너지를 계산하여 더해준다. (ex. 1→2인경우 + 2→1인 경우)

---

결론

---

해당 문제를 푸는데 최소 1시간은 걸린 것 같다..

문제를 풀다보니, 앞에서 풀었었던 문제들과 유사한 패턴이 보여 이를 적용하니 문제가 해결되어서 매우 재밌었다.

자꾸 이상한 값이 나오길래, 브레이크를 걸고 열심히 디버깅하니 해결할 수 있었다!!.

---

열심히 디버깅한 흔적..ㅎ

---