알고리즘 공부

[백준 15661번] 링크와 스타트 - java

철매존 2024. 12. 1. 02:05
728x90
반응형

문제 설명

1. N X N 게임판이 있다.

2. 사람들이 주어지고 각 능력치의 합이 있다.

3. 팀을 나눠서 전체 팀원들의 능력치 합을 구한다.

4. 모든 사람들이 포함되어야 한다. 사람들의 숫자가 같지는 않아도 된다.

5. 참고로 같은 팀에 있는 사람들의 모든 능력치 합을 구해야 한다.

(문제 설명이 진짜 역대급으로 불친절하다. 일부러 헷갈리게 한게 아닌가 의심될 정도)

풀이 과정

1. BF + DFS + 백트래킹

2. 비트마스킹을 이용할 수 있다고는 하는데, 2개 케이스에 대해 각각 계산을 해도 터지지는 않을 것 같아 비트마스킹을 쓰지는 않았다. 좀 오래걸리지만 그래도 통과함 -> O(n^22^2)

3. 간단히 말하자면 team1, team2 에 모든 사람을 각각 넣어가면서 확인하고, 그래서 모든 사람에 대한 팀배정이 완료되면 그걸 확인해주면 되는 방식이다.

코드

import java.util.*;

public class Main {
    private static int[][] map;
    private static List<Integer> team1 = new ArrayList<>();
    private static List<Integer> team2 = new ArrayList<>();
    private static int ans = Integer.MAX_VALUE;
    private static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];

        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        dfs(0);

        System.out.println(ans);
    }

    private static void dfs(int index) {
        // 모든 팀을 나눈 후에는
        if (index == N) {
            // 각 팀의 능력치를 계산하고
            int team1Sum = calculateScore(team1);
            int team2Sum = calculateScore(team2);

            // 능력치 합의 차이를 구한다.
            ans = Math.min(ans, Math.abs(team1Sum - team2Sum));
            return;
        }

        // team1에 지금 사람을 넣고, dfs 시작
        team1.add(index);
        dfs(index+1); // 다음사람에 대한 추가 or 전체 사람에 대한 확인
        team1.remove(team1.size()-1); // 이번사람에 대한 확인이 끝나면, 다시 빼준다.

        // 이사람을 다시 team2에 넣고, dfs 시작
        team2.add(index);
        dfs(index+1);
        team2.remove(team2.size()-1);
    }

    private static int calculateScore(List<Integer> team) {
        int score = 0;

        // 맵에서 팀원들의 모든 능력치 합산
        for (int i=0; i<team.size(); i++) {
            for (int j=0; j<team.size(); j++) {
                score += map[team.get(i)][team.get(j)];
            }
        }

        return score;
    }
}



반응형