[추천문제] 백준 14889: 스타트와 링크 - javascript(완전탐색)

현재 백준 등급 

(지금은 실버2 등급이다.) 

 

후기 

아직 문제의 끝 마무리는 못한다. 

그래도 이제 어떤 방식으로 풀어내야 하는지 전체 그림은 알고 있다.  그리고 99% ? 코드 구현을 거의 비슷하게 하지만 

1% 정도 문법을 잘 몰라서, 예를 들어 return을 언제 써야 하는지 몰라서, 이 문제에서는 K를 작성하지 않아서,,  딱 정답을 맞히지는 못하고 있다. 

하지만 정말 많이 성장했음을 느낀다. 

애초에 쉬운 task 였다면 난 이 속에서 즐거움을 느끼지 못했을 것이다. 

내가 하면 할수록 더 잘 풀 수 있다는게 확실히 느껴지고, 

난 더 잘 풀고 싶다. 

더 잘해내고 싶다. 

잘 해낼 수 있을 거라 믿는다. 

절실한 마음과 강력한 행동은 내게 기회를 잡을 힘을 준다. 

 

문제 추천 이유 

- 탐색의 2가지 방법을 다 배울 수 있다. 

=> dfs를 이용해서 여러 사람을 2팀으로 나누는 방법

=> 이중 반복문을 이용해서 2명씩 팀을 나누는 방법

 

문제 출처 

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

14889번: 스타트와 링크

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

	1	2	3
4		5	6
7	1		2
3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력 1 복사

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력 1 복사

0

예제 입력 2 복사

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

예제 출력 2 복사

2

예제 입력 3 복사

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

예제 출력 3 복사

1

문제 풀이 구성 

 

- 팀을 나누는 완전 탐색을 해야 한다. => dfs 활용 

- 팀 내에서 2명씩 짝짓는 완전 탐색을 해야 한다. => 이중반복문 활용

- 위 2 명 짝 지었을 때 팀에 보태는 능력치를 계산하는 함수를 따로 만들어준다. 

- 두 팀의 능력치 차이를 비교해서 최소값을 구한다. 

 

코드 잘라서 분석 

팀을 나누는 dfs 완전탐색 방법중이다. 

예를 들어 ) N이 4일 때, 

한 팀은 2명이 된다. 

그래서 L === 2가 되는 모든 경우의 수를 구한다. 

그런데, 왜 dfs(_,_) 두개의 인자가 필요하냐고? 

시간이 초과되기 때문이다. 

player[1]이 확정일 때, player[2]부터 확인하면 된다. 

player[2]가 확정일 때, player[3]부터 확인하면 된다. 

즉, 불필요한 계산을 없애기 위함이다 ! 

 

player 배열에서 true로 되어 있는 값을 

spark 팀으로 ! 

false값으로 되어있다면 

link 팀으로 ! 

보내버린다. 

 

구한 두 팀을 twoPeople 함수의 매개변수로 넣어준다. 

그 때 나오는 값은 

두 팀의 총 능력치의 차이다. 

우리는 두 팀의 총 능력치 차이가 적은 것으로 계속 answer 값을 대체해준다. 

 

 

팀 안에서도 두명씩 짝을 지어서 능력치를 구해야 한다. 

예를 들어 ) 

spark = [1,3,5]

link = [2,4,6]

일 때, 

위 반복문에 들어가면 ~~ 

spark1 과 spark 3 의 능력치 

그다음은 spark 1, spark 5 의 능력치

그 다음은 spark3, spark5 의 능력치

를 팀의 총 능력치에 계속 더해준다. 

getPower 라는 함수에 두 선수를 넣으면 능력치를 계산해주도록 할 것임. 

 

 

제일 쉬운 부분 ^^ 

두 선수가 이 함수에 들어오면 

팀에 더해지는 능력치를 return 해줄 것이다 ! 

 

 

정답 풀이 코드

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')
const N = Number(input.shift()); 
const graph = input.map(v=> v.split(' ').map(Number)); 
let player = new Array(N+1).fill(false); 
let answer = Number.MAX_SAFE_INTEGER; 

function dfs(L,K){
    if(L === N/2){
        let spark = []; 
        let link = []; 
        for(let i=1; i<=N; i++){
            if(player[i] === true){
                spark.push(i);
            }else{
                link.push(i);
            }
        }
        let value = twoPeople(spark, link); 
        answer = Math.min(answer, value); 
        return; 
    }else{
        for(let i=K; i<=N; i++){
         if(!player[i]){
        player[i] = true; 
        dfs(L+1,i+1); 
        player[i] = false;     
            }   
        }
    }
    return; 
}
dfs(0,1);


function twoPeople(spark, link){
    let sparkPower = 0; 
    let linkPower = 0; 
     for(let i=0; i<spark.length-1; i++){
         for(let j=i+1; j<spark.length; j++){
            sparkPower += getPower(spark[i], spark[j]); 
            linkPower += getPower(link[i], link[j]);  
         }
     }
    return Math.abs(sparkPower - linkPower); 
}

function getPower(i,j){
    let power = 0; 
    power = graph[i-1][j-1] + graph[j-1][i-1]
    return power; 
}
console.log(answer);

 

의사 코드 추가 

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')
const N = Number(input.shift()); 
const graph = input.map(v=> v.split(' ').map(Number)); 
let player = new Array(N+1).fill(false); //선수는 1부터 N까지 있다. 
let answer = Number.MAX_SAFE_INTEGER; 

//dfs를 이용한 완탐으로 팀이 될 수 있는 경우의 수를 구한다. 
//K를 작성하지 않으면 시간초과가 된다. 
function dfs(L,K){
    if(L === N/2){
        let spark = []; 
        let link = []; 
        for(let i=1; i<=N; i++){
            if(player[i] === true){
                spark.push(i);
            }else{
                link.push(i);
            }
        }
        let value = twoPeople(spark, link); 
        answer = Math.min(answer, value); 
        return; 
    }else{
        for(let i=K; i<=N; i++){ //ex) 선수 1을 상대할 때는 선수 2부터 따지면 된다 
         if(!player[i]){
        player[i] = true; 
        dfs(L+1,i+1); 
        player[i] = false;     
            }   
        }
    }
    return; 
}
dfs(0,1);

//dfs를 이용해서 한 팀에 있는 사람들을 두명씩 짝짓는다. 
function twoPeople(spark, link){
    let sparkPower = 0; 
    let linkPower = 0; 
     for(let i=0; i<spark.length-1; i++){
         for(let j=i+1; j<spark.length; j++){
            sparkPower += getPower(spark[i], spark[j]); 
            linkPower += getPower(link[i], link[j]);  
         }
     }
    return Math.abs(sparkPower - linkPower); 
}

//그 두명이 팀에 보태는 파워 
function getPower(i,j){
    let power = 0; 
    power = graph[i-1][j-1] + graph[j-1][i-1]
    return power; 
}
console.log(answer);