[알고리즘] 백준 14889 스타트와 링크 -백트랙킹- 자바 코틀린

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

백준 14889 스타트와 링크 문제를 풀어봤습니다. 

 

주어진 인원 수와 그 인원들끼리의 시너지 점수가 담긴 2차원 배열을 보고 가장 격차가 적게 스타트팀, 링크팀 두 개의 팀을 짜는게 목표인 문제입니다.

 

처음 풀이는 시간초과가 났는데 원인은 조합이 아닌 순열로 탐색을 했기 때문이었습니다. 주의해야겠습니다.

 

1. 두 개의 팀을 나누니까 인원수의 1/2 만큼 탐색을 하면 탐색을 종료합니다.

2. 1번을 위해 isVisted[] boolean 배열을 선언합니다. 

3. 현재 사람과 맺어진 팀원의 인덱스의 +1(조합을 위헤)과 방문한 개수로 dfs()를 돌립니다.

 

 

 

 

 

[Java 시간초과 순열탐색]

import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static boolean[] isVisited;
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        map = new int[size][size];
        isVisited = new boolean[size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        dfs(0);
        System.out.println(min);
    }

    private static void dfs(int index) {
        if (index == map.length / 2) {
            int startTeam = 0;
            int linkTeam = 0;
            for (int i = 0; i < map.length - 1; i++) {
                for (int j = i + 1; j < map.length; j++) {
                    if (isVisited[i] && isVisited[j]) {
                        startTeam += (map[i][j] + map[j][i]);
                    } else if (!isVisited[i] && !isVisited[j]) {
                        linkTeam += (map[i][j] + map[j][i]);
                    }
                }
            }
            min = Math.min(min, Math.abs(startTeam - linkTeam));
            return;
        }
        for (int i = 0; i < map.length; i++) {
            if (!isVisited[i] && index != i) {
                isVisited[i] = true;
                dfs(index + 1);
                isVisited[i] = false;
            }
        }

    }
}

 

 

 

[Java 맞는 풀이 -조합-]

import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static boolean[] isVisited;
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        map = new int[size][size];
        isVisited = new boolean[size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    private static void dfs(int index, int depth) {
        if (depth == map.length / 2) {
            int startTeam = 0;
            int linkTeam = 0;
            for (int i = 0; i < map.length - 1; i++) { //방문, 비방문 두개의팀으로 전체 시너지 합산
                for (int j = i + 1; j < map.length; j++) {
                    if (isVisited[i] && isVisited[j]) {
                        startTeam += (map[i][j] + map[j][i]);
                    } else if (!isVisited[i] && !isVisited[j]) {
                        linkTeam += (map[i][j] + map[j][i]);
                    }
                }
            }
            min = Math.min(min, Math.abs(startTeam - linkTeam));
            return;
        }
        for (int i = index; i < map.length; i++) { //조합탐색
            if (!isVisited[i]) {
                isVisited[i] = true;
                dfs(i + 1, depth + 1);
                isVisited[i] = false;
            }
        }

    }
}

 

 

[Kotlin]

import java.util.*

lateinit var map: Array<IntArray>
lateinit var isVisited: BooleanArray
private var min = Integer.MAX_VALUE

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val size = sc.nextInt()
    map = Array(size) { IntArray(size) }
    isVisited = BooleanArray(size)
    for (i in 0 until size) {
        for (j in 0 until size) {
            map[i][j] = sc.nextInt()
        }
    }
    dfs(0, 0)
    println(min)
}

private fun dfs(index: Int, depth: Int) {
    if (depth == map.size / 2) {
        var startTeam = 0
        var linkTeam = 0
        for (i in 0 until map.size - 1) {
            for (j in i + 1 until map.size) {
                if (isVisited[i] && isVisited[j]) {
                    startTeam += map[i][j] + map[j][i]
                } else if (!isVisited[i] && !isVisited[j]) {
                    linkTeam += map[i][j] + map[j][i]
                }
            }
        }
        min = Math.min(min, Math.abs(startTeam - linkTeam))
        return
    }
    for (i in index until map.size) {
        if (!isVisited[i]) {
            isVisited[i] = true
            dfs(i + 1, depth + 1)
            isVisited[i] = false
        }
    }

}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!