14889번

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

14889번: 스타트와 링크

 

이번 문제는 많은 감자짓을 통해 해결한 문제이다. 알고리즘 장인 선배의 도움이 없었다면 못풀고 몇일을 고민하다 답지 봤겠지..

 

처음 이 문제를 봤을 때 문제의 이해를 조금 잘못해서 삽질의 시간이 좀 더 오래걸렸다. 나는 팀을 주어진 수에서 2명씩 골라서 2팀을 만드는 문제인줄 알고 삽질하다가 선배가 문제 설명해줘서 이해하고 접근을 시작했다. 그런데도 접근 방법이 떠오르지 않아서 도움을 통해 접근했다...ㅎㅎ

 

그래서 이 문제의 접근 방법은 이렇다.

먼저 N명의 사람이 있고 이들을 정확히 절반씩 나누어 팀을 이루는 것이다. 그렇게하여 각팀원들 간의 경험치 시너지를 계산하여 두팀의 경험치 시너지 차가 최소로 되게끔 만드는 것이다.

 

먼저 팀의 경험치 시너지는 고려하지 않고 팀을 나누는 것을 중점으로 생각해야한다.

그러면 완전 트리 구조를 떠올릴 수 있다면 떠올릴 것이다.(나는 못함...)

 

1번부터 N번까지의 사람이 스타트팀과 링크팀으로 가는 경우를 생각해서 트리를 그리면된다.

순서대로 1번부터 N번까지의 사람을 두 팀으로 나눈다면, 일단 1번을 스타트팀에 넣는 경우와 링크팀에 넣는 경우로 생각하면

아래의 트리구조를 그릴 수 있다. 

 

그림이 좀 균형 안 맞아도 이해해주세요:)

따라서 처음에 1번이 스타트팀에 들어가고 2번도, 3번도, 4번도 다 스타트팀에 들어가면 링크 팀과 절반으로 나누어 떨어지지 않기 때문에 성립하지 않을 것이다. 그렇기에 백트래킹을 여기서 사용하는 것이다.

다시 4번에서 3번으로 올라가서 4번이 링크 팀으로 가는경우, 역시 절반이 아니라서 성립하지 않는다. 그럼 다시 3번에서 2번으로 올라간다. 그럼 3번이 링크팀으로 가고, 4번이 스타트팀으로 가는 경우와 링크팀으로 가는 경우로 나뉜다. 그럼 1번 4번이 스타트팀이고 2번 3번이 링크팀인 경우는 성립하기에 그때 팀의 경험치 시너지 차이를 구해주면 된다. 그럼 코드를 보면서 이해를 해보자.

코드를 보면서 생각하는게 이해가 더 쉬울수도 있다.

 

// here 번째 사람부터 start 팀 또는 link 팀에 넣기 시작할 때,
// 두 팀의 능력치 차이의 최솟값을 반환하는 함수
public int dfs(int here, Stack<Integer> start, Stack<Integer> link) {
    // 전부 다 골랐으면 두 팀의 능력치 차이 계산
    if (here == v+1) {
        if (start.size() == link.size()) {
            sum = 0;
            int N = start.size();
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    sum += matrix[start.get(i)-1][start.get(j)-1];
                    sum += matrix[start.get(j)-1][start.get(i)-1];
                    sum -= matrix[link.get(i)-1][link.get(j)-1];
                    sum -= matrix[link.get(j)-1][link.get(i)-1];
                }
            }
            // sum 계산
            return Math.abs(sum);
        }
        else return 987654321;
    }
    // here 번째 사람을 start 팀에 넣는 경우
    start.add(here);
    int left = dfs(here + 1, start, link);
    start.pop();
    // here 번째 사람을 link 팀에 넣는 경우
    link.add(here);
    int right = dfs(here + 1, start, link);
    link.pop();
    // 둘 중에 최솟값 반환
    min = Math.min(left,right);
    return min;
}

위의 코드에서 DFS 구조를 사용한 부분은 here번째 사람을 start팀에 넣고 dfs를 돌려서 백트래킹하는 부분이다.

위 코드를 사용하여 디버깅을 해보면 알 수 있을 것인데, 위에 그려놓은 트리에서 맨밑으로 내려간 후 다시 위로 올라가면서 비교해보는 과정을 구현한 것이라고 생각하면 된다.

N=4라고 했을 때 처음에 스타트 팀으로 1,2,3,4번 모두가 start팀에 들어가면 if문을 통해 두팀이 반으로 정확히 나눠지지 않았음을 처리한다. 즉 반환 값을 INF(나오지 않게 만들 수)로 지정하여 절대 최솟값으로 나오지 못하게 반환한다. 그리고 4번을 링크팀으로 옮기고 다시 조건문을 확인하여 또 나눠지지 않았음으로 INF로 반환하고, 왼쪽 즉 4번이 스타트팀에 들어갔을 때 나온 반환값과 4번이 링크팀으로 들어갔을 때 나온 반환값을 비교하여 최소값으로 지정하고 4번은 링크 리스트에서 빼서 다시 3번의 위치로 돌아온다.

그럼 3번의 지점은 left = dfs 부분 밑으로 온다. 그럼 3을 빼내고 3번을 링크 팀으로 옮겨 넣는다. 그 다음 4번을 스타트팀에 넣는 경우와 링크팀에 넣는 경우를 위에서처럼 반복한다. 그러면 1번이 스타트팀이고, 2번이 링크팀이고, 3번이 스타트팀, 4번이 스타트팀과 4번이 링크팀인 경우를 계산하고(1스,2링,3스,4스)/(1스,2링,3스,4링), 그다음 1번이 스타트팀, 2번이 링크팀, 3번이 링크팀, 4번이 스타트팀과 4번이 링크팀인 경우를 계산한다(1스,2링,3링,4스)/(1스,2링,3링,4링).여기서 if문에 들어가는 경우는 2개이고, 그들을 통해 sum값을 반환하면, 그 값을 맨 밑부분에서 더 작은 값을 찾아 반환한다.

 

이 문제를 이해하면 백트래킹이 뭔지 이해할 수 있다고 생각한다. 그림을 그리면서 생각하보면 백트래킹이 뭘 의미하는지 이해할 수 있다.

 

정답 코드는 아래와 같다.

package backjoon;

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

public class b14889 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] arr = new int[N][N];
        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());
            }
        }//행렬 받아오기
        gp g = new gp(N,arr);
        Stack<Integer> start = new Stack<>();
        Stack<Integer> link = new Stack<>();
        System.out.println(g.dfs(1,start,link));
    }
}
class gp{
    int v;
    Stack<Integer> start;
    Stack<Integer> link;
    int min;
    int sum=0;
    int[][] matrix;
    ArrayList<Integer> st;
    ArrayList<Integer> li;
    public gp(int v, int[][] matrix){
        this.v = v;
        this.matrix = matrix;
        start = new Stack<>();
        link = new Stack<>();
        st = new ArrayList<>();
        li = new ArrayList<>();
    }

    // here 번째 사람부터 start 팀 또는 link 팀에 넣기 시작할 때,
    // 두 팀의 능력치 차이의 최솟값을 반환하는 함수
    public int dfs(int here, Stack<Integer> start, Stack<Integer> link) {
        // 전부 다 골랐으면 두 팀의 능력치 차이 계산
        if (here == v+1) {
            if (start.size() == link.size()) {
                sum = 0;
                int N = start.size();
                for (int i = 0; i < N; i++) {
                    for (int j = i + 1; j < N; j++) {
                        sum += matrix[start.get(i)-1][start.get(j)-1];
                        sum += matrix[start.get(j)-1][start.get(i)-1];
                        sum -= matrix[link.get(i)-1][link.get(j)-1];
                        sum -= matrix[link.get(j)-1][link.get(i)-1];
                    }
                }
                // sum 계산
                return Math.abs(sum);
            }
            else return 987654321;
        }
        // here 번째 사람을 start 팀에 넣는 경우
        start.add(here);
        int left = dfs(here + 1, start, link);
        start.pop();
        // here 번째 사람을 link 팀에 넣는 경우
        link.add(here);
        int right = dfs(here + 1, start, link);
        link.pop();
        // 둘 중에 최솟값 반환
        min = Math.min(left,right);
        return min;
    }
}