[JAVA] 백준, 14889번 스타트와 링크

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

풀이

처음에는 스타트 값을 더하기위해 인덱스를 저장한 배열, 링크를 위한 배열을 별도로 생성했다. 근데 도저히 코드로 어떻게 풀어나가야할지 떠오르지가 않아 다른 사람의 방법을 선택했다.

 

visited 배열을 사용하여 true인 인덱스는 start에 더하고, false는 link에 더한다. dpeth가 N / 2일 때 계산을 하는 이유는 문제에서 설명하길 팀 인원은 N / 2명이라고 명시되어 있기 때문이다.

 

calculate()에서 i의 범위를 N까지하면 j와 중복되는 인덱스가 발생하기 때문에 N - 1로 설정한다. 

N이 4일 때의 예시이다.

• i = 0
  • j = 1, 2, 3
• i = 1
  • j = 2, 3
• i = 2
  • j = 3
• i = 3
  • j = 3

코드

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

public class Main {

    static int N;
    static int[][] arr;
    static int min = Integer.MAX_VALUE;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N];
        arr = new int[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0);
        System.out.println(min);
    }

    static void dfs(int depth, int idx) {
        if (depth == N / 2) {
            calculate();
            return;
        }

        for (int i = idx; i < N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(depth + 1, i + 1);
                visited[i] = false;
            }
        }
    }

    static void calculate() {
        int start = 0;
        int link = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (visited[i] && visited[j]) {
                    start += arr[i][j] + arr[j][i];
                } else if (!visited[i] && !visited[j]) {
                    link += arr[i][j] + arr[j][i];
                }
            }
        }

        min = Math.min(min, Math.abs(start - link));
    }
}