14889. 스타트와 링크 (Java, 자바)

아니 스크린샷 번짐이 왜이리 심하지?...

아무튼간에 오랜만에 업로드. 백준허브로 업로드할시, 정답 코드만 저장할 수 있어서,

틀린 경우, 오답노트처럼 기록하기에는 블로그가 나을것 같아

시간초과나 오답노트가 필요한 문제만 블로그에 기록하기로 했다.

 

일단 내가 알고있는 지식 : N과M 시리즈처럼 줄세우기 인데,

이걸 응용해서, start 팀을 줄세우고, 그 외에 구성원을 link팀으로 보내는 것이었다.

그 전후 과정은 그리 어렵지 않았으니...

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[][] s;
    static int[] start; //스타트팀
    static List<Integer> link; // 링크팀
    static boolean[] visit; // 방문여부를 판별하는 배열
    static boolean[] sl; // 스타트팀과 링크팀을 구분하는 배열
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n][n];
        visit = new boolean[n];
        start = new int[n/2];
        StringTokenizer st;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<n; j++) {
                s[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0);
        System.out.println(min);
    }

    static void dfs(int depth) {
        if (depth == 0) {
            sl = new boolean[n];
        }
        if (depth==n/2) {
            link = new ArrayList<>(n/2);
            int k = 0;
            for (int i=0; i<n; i++) {
                if (!sl[i]) {
                    link.add(i);
                }
            }

            for (int i=0; i<n/2-1; i++) {
                for (int j=i+1; j<n/2; j++) {
                    k+=(s[start[i]][start[j]]+s[start[j]][start[i]]
                        -s[link.get(i)][link.get(j)]-s[link.get(j)][link.get(i)]);
                }
            }
            min = Math.min(min, Math.abs(k));
            return;
        }

        for (int i=0; i<n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                start[depth] = i;
                sl[i] = true;
                dfs(depth+1);
                visit[i] = false;
                sl[i] = false;
            }
        }
    }
}

IDE에서 출력시 정답은 잘 나왔는데, 제출시 시간초과가 걸림.

코드를 짜며 헤맸던 부분은, start팀과 link팀의 자료형이었다. start팀은 줄세울수 있다치자. link팀은 어쩔거임?

n명의 구성원에서, start팀을 제외한 나머지를 처리해줘야하는데, 이런 경우 start팀을 set자료형처럼 순서는 없지만 존재유무로만 판별해주면 쉽다. 그런데, 순서를 구분하지 않으면, 후속처리가 곤란해진다.

그래서 크기가 지정된 ArrayList로도 해봤는데, capacity는 size와는 또 다른 개념이라, 내가 생각한대로 먹혀들지 않았다.

결국 start팀은 배열로, link팀은 ArrayList로 받는 타협책을 내놨지만, 시간초과로 막힘.

 

그리고 코드를 짜면서 느꼈는데, start팀과 link팀을 판별하는 boolean인 sl이 방문여부를 따지는 visit와 겹친다는 생각이 들었다. 그도 그럴것이, '깊이우선탐색'으로 방문한 노드들은 전부 'start팀의 구성원' 으로 들어가기 때문. 따라서 이를 따로 판별해줄 필요가 없다.

 

결국 정답을 보았는데, 기본적인 실수가 하나 있었다. 내림/오름차순으로 중복을 허용하지 않는 N과 M은, index 값을 인자로 따로 받았다는 것. 추가적으로, 내가 생각한대로 visit만 있어도 start와 link팀을 나누는데 무리가 없었고, 그에 따라 start팀과 link팀을 굳이 컬렉션으로 모아줄 필요가 없었다는 것이다. 그냥 visit 상태에 따라 나눠서 판별해주면 되었다.

 

정답을 보고 개량하여 제출하여 완료.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[][] s;
    static boolean[] visit; // 방문여부를 판별하는 배열
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n][n];
        visit = new boolean[n];
        StringTokenizer st;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<n; j++) {
                s[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    static void dfs(int index, int depth) {
        if (depth==n/2) {
            diff();
            return;
        }

        for (int i=index; i<n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(i+1,depth+1);
                visit[i] = false;
            }
        }
    }

    static void diff() {
        int teamStart = 0;
        int teamLink = 0;

        for (int i=0; i<n-1; i++) {
            for (int j=i+1; j<n; j++) {
                // i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스
                if (visit[i] && visit[j]) {
                    teamStart += s[i][j];
                    teamStart += s[j][i];
                }
                // i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스
                else if (!visit[i] && !visit[j]) {
                    teamLink += s[i][j];
                    teamLink += s[j][i];
                }
            }
        }

        // 두 팀의 점수차이
        int ans = Math.abs(teamStart-teamLink);

        if (ans==0) {
            System.out.println(ans);
            System.exit(0);
        }

        min = Math.min(min, ans);
    }
}