lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이 문제는 재귀를 통한 백트래킹 유형으로 풀 수 있는 문제 중 하나이다.


아이디어 도출

N이 4일 때, 즉 4명의 사람이 있을 경우 2팀으로 나누어 조합을 톨해 경우의 수를 구해야 한다. 그 경우의 수는 다음과 같다.

1
2
3

[(1, 2), (3, 4)],
[(1, 3), (2, 4)],
[(1, 4), (2, 3)]

이를 통해 구할 수 있는 스타트 팀과 링크 팀의 능력치를 다음과 같이 구할 수 있다.

1
2
3

[5(S12 + S21), 7(S34, S43)] = 2,
[9(S13, S31), 10(S24, S42)] = 1,
[6(S14, S41), 6(S23, S32)] = 0

위 조합에서 팀 간의 점수 차가 가장 낮은 방법은 1번과 4번이 한 팀, 2번과 3번이 한 팀이었을 때이다! 이와 같이 모든 조합의 경우의 수를 탐색해가며 두 팀 간 능력치의 차가 최솟값이 되는 조합 방법을 찾으면 된다.

문제풀이를 위한 아이디어는 다음과 같다.

  1. N/2 만큼 사람을 구분하여 팀을 나누기 때문에, 재귀 호출을 하며 재귀의 깊이가 N/2가 되면 종료한다.
  2. 방문 배열에 방문한 노드의 페어로 같은 팀을 구분하여 스타트팀과 링크 팀의 점수를 구한다.
  3. 두 팀의 점수차의 절댓값을 구한 후 출력한다.

두 팀의 점수차가 0점이라면 이미 최소이기에 탐색을 더 진행할 필요가 없다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

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

class Main {    

    // 방문배열과 입력배열 선언
    static boolean[] visited;
    static int[][] arr;    

    // 배열의 크기 N 선언
    static int N;

    // 최솟값을 담을 변수 선언
    static int min;

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            
                N = Integer.parseInt(br.readLine());

                arr = 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++) {
                        arr[i][j] = Integer.parseInt(st.nextToken());
                    }
                }

                // 최솟값 갱신을 위한 min 초기화.
                min = Integer.MAX_VALUE;

                // dfs 함수 호출
                dfs(0, 0);

                bw.write(min+"\n");

        }

    }

    /**
     * idx: 인덱스
     * depth: 재귀의 깊이, 조합 개수
     */
    public static void dfs(int idx, int depth) {

        // N/2 번만큼 반복후 종료한다.
        if(depth == N / 2) {
            
            // 스타트 팀과 링크 팀의 점수를 구하기 위한 초기화.
            int start = 0;
            int link = 0;

            // 방문한 팀과 방문하지 않은 팀을 나누어 팀의 점수를 구하고 최솟값을 찾는다.
            for(int i=0; i<N-1; i++) {
                for(int j=i+1; j<N; j++) {

                    // i번째와 j번째 사람이 true라면, start team이다.
                    if(visited[i] == true && visited[j] == true) {
                        start += arr[i][j];
                        start += arr[j][i];
                    }
                    // i번째와 j번째 사람이 fals라면, link team이다.
                    else if(visited[i] == false && visited[j] == false) {
                        link += arr[i][j];
                        link += arr[j][i];
                    }
                }
            }

            // 두 팀의 점수 차이 절댓값을 구한다.
            int result = Math.abs(start - link);

            // 만약 두 팀의 점수 차가 0이라면 가장 최솟값이기에 바로 죵료한다.
            if(result == 0) {
                min = 0;
                return;
            }
            
            min = Math.min(min, result);

        }

        // N까지 반복해가며 방문하지 않았다면 아래 내용 수행
        // 방문 처리 -> 재귀 호출 -> 방문 처리 해제
        for(int i=idx; i<N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(i+1, depth+1);
                visited[i] = false;
            }
        }

    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy